This study aims to improve the accuracy of predicting new student major selection using the Gradient Boosting algorithm optimized through hyperparameter tuning. Gradient Boosting was chosen for its ability to handle complex and diverse data, which is crucial in the context of major prediction. The data used was sourced from the new student admissions database of Universitas Islam Nahdlatul Ulama Jepara for the 2013–2023 period, with preprocessing including data cleaning, imputation of missing values, and transformation of categorical features. The initial accuracy of the Gradient Boosting model with default configuration reached 99.01%, indicating that the dataset had relatively clear and structured patterns, enabling the baseline model to perform highly. However, to ensure generalization and avoid the risk of overfitting, hyperparameter tuning was performed using Randomized Search CV. The tuning results showed an increase in accuracy to 99.84% with optimal configurations including a learning rate of 0.1, 300 estimators, and a maximum tree depth of 4. Feature analysis also revealed that attributes such as "school_type," "school_origin," and "gender" significantly influenced the prediction outcomes. This study demonstrates that hyperparameter tuning can significantly enhance model performance, providing a more accurate and relevant predictive solution for the major selection process. Nevertheless, the study's limitation lies in the scope of the dataset, which originated from a single institution, suggesting the need for further exploration with more diverse data and advanced tuning methods like Bayesian Optimization. These findings provide valuable contributions to educational institutions in developing data-driven systems to support strategic decision-making.