In the context of the labor market is volatile, requires candidates to have the ability and skills to match the needs of the employers. However, most recent graduates have difficulty finding jobs that match their abilities. At the same time, assessing the ability of candidates and selecting the right candidates for the job is a huge challenge for the employers. In this paper, we introduce a new approach to early prediction the employable of students in Vietnam after graduation by using some machine learning methods: Gaussian Naive Bayes (NB), Support Vector Machine (SVM), Decision Tree (DT), Random Forest (RF), and Artificial Neural Network (ANN). We collect data about students from the graduation year of 2020 and 2021, including learning scores, working environment, and personal information such as gender, hometown. After that, we create three models to early predict the students employment status from learning data of first academic year (Model_1), after the first two years of study (Model_2) and fourth year (Model_full). Beside that, three more models have been created from learning data about the subjects of ideological and political (Model_3), pedagogical skills (Model_4), foreign language skills (Model_5). Furthermore, we trying to improve the performance of the models through sampling methods such as: Synthetic Minority Oversampling Technique (SMOTE – Over-sampling), Edited Nearest Neighbors (ENN – Under-sampling) and SMOTE_ENN (Hybrid-sampling). Experimental results show that ANN methods bring the best performance to predict student employment status with accuracy up to 80% for the test dataset. Moreover, Model_1 brings positive results in terms of early prediction of student’s employment status after the first year of study with an accuracy for about 70% on the test dataset.