The sonic log is an essential petrophysical log and it is used in many petroleum applications (seismic and geomechanically applications). Since sonic logs are hard to acquire and expensive to run in all boreholes, oil companies conduct them in a few wells. Thus, several petrophysical and geophysical workflows incorporate sonic log synthetization. Empirical correlations or statistical methods are conventional methods to estimate the sonic value. Despite the advantages of simple correlations for quick estimations, these traditional approaches are not as powerful as modern-day machine learning techniques. This study presents combining different Machine learning and Feature Selection algorithms that were applied to predict highly accurate synthetic sonic logs from basic petrophysical logs. Machine learning algorithms have been implemented for this purpose, including Multi-Regression (ML), Artificial Neural Network (ANN), Support Vector Machine (SVM), and Random Forest (RF). This study is implemented with data from seven wells in North Oman's tight gas sandstone. To highlight which of the logs will be good predictors of sonic logs, feature selection approaches were carried out. Approximately 70% of the data was used for model training, while the rest was used for testing and validation. Analyzing the logs of the measured wells serves as a means of determining the efficiency of the built models. This implies that compared to other algorithms, the Hybrid Random Forest algorithm with a backward elimination feature selection approach can be an efficient way of predicting the sonic logs and yielding a very high correlation coefficient of more than 0.95 %. For geomechanical applications, this method will provide enhanced sonic prediction and is especially important for prospective wells where logs of sonic suits do not need to be acquired which ultimately leads to effective cost-effective solution.