Accurately predicting the lifetime of lithium-ion batteries in early cycles is crucial for ensuring the safety and reliability, and accelerating the battery development cycle. However, most of existing studies presented poor prediction results for early prediction, due to the nonlinear battery capacity fade with negligible variation in early cycles. In this paper, to achieve an accurate early-cycle prediction of battery lifetime, a comprehensive machine learning (ML) based framework containing three modules, the feature extraction, feature selection, and machine learning based prediction, is proposed. First, by analysing the evolution pattern of various informative parameters, forty-two features are manually crafted based on the first-100-cycle charge-discharge raw data. Second, to manage feature irrelevancy and redundancy, four typical feature selection methods are adopted to generate an optimal lower-dimensional feature subset. Finally, the selected features are fed into six representative ML models to effectively predict the battery lifetime. Numerical experiments and paired t-test are conducted to statistically evaluate the performance of the proposed framework. Results show that the wrapper-based feature selection method outperforms other methods, and significantly improves the prediction performance of subsequent ML models. Both before and after wrapper feature selection, the elastic net, Gaussian process regression, and support vector machine present better performance than other complex ML prediction models. The support vector machine model combined with wrapper feature selection statistically presents the best result for battery lifetime prediction, with a root-of-mean-square-error of 115 cycles, and a R² of 0.90. Finally, when compared with an existing work, the root-of-mean-square-error is substantially decreased from 173 to 115 cycles, by using the proposed framework.