This article is concerned with machine learning (ML) algorithms when data suffers from two common problems namely, missing values and outliers where both problems can be a main cause for efficiency degradation of the ML predictive models. Six ML algorithms are used to predict the Cleveland heart disease dataset where this data suffers from outliers. The performances of these algorithms are measured in terms of metrics namely; accuracy, kappa statistic, F1 score and our suggestion in using the geometric mean. To overcome the negative impacts of outliers and missing values, we proposed a technique called treatment of outlier data as missing values by applying imputation methods (TOMI) instead of the classical method by removing these outliers. Four methods were applied to impute missing data namely, mean, median, K-Nearest Neighbor (KNN) and Random Forest (RF), where the KNN method outperformed the other different methods in terms of mean absolute error (MAE) and root mean square error (RMSE) in imputing the missing values. There are two scenarios on splitting our dataset namely; first: 60-40% and second: 75-25%. Based on the first scenario, the Naive Bayes (NB) algorithm showed the highest performance (in all metrics); for instance, in accuracy it achieved 85.12% and 87.6% before and after applying TOMI respectively. While in the second scenario, the Logistic Regression (LR) algorithm showed the highest performance (in all metrics); again for accuracy it achieved 86.67% and 89.33% before and after applying TOMI respectively. To conclude, the NB and LR algorithms predict our dataset better than other used algorithms. Moreover, the applied TOMI technique enhances the efficiency of the entire ML algorithms, which makes the predictive models possess more accurate results.