We develop and test a method that can be applied generally by hospitals to improve readmission prediction. Relying on state-of-the art machine learning algorithms, we predict the probability of 30-day readmission at initial admission and at discharge using administrative data on 1,633,099 hospital stays in Quebec between 1995 and 2012. Deep Learning produces excellent predictions of readmission province-wide, and Random Forest reaches similar levels. The area under receiver operating characteristic curve for these two algorithms reaches over 78% at hospital admission and over 87% at hospital discharge, and the diagnostic codes are among the most predictive variables. The ease of implementation of machine learning algorithms, together with objectively validated reliability, brings new possibilities for cost reduction in the health care system.