Over the past decade, researchers investigated incorporating carbon nanotubes (CNTs) to improve the mechanical properties of cementitious materials. Recently, few studies developed Machine Learning (ML)-based predictive models to maximize insights from limited experimental data. However, these models often fail to identify key parameters and their complex correlations with mechanical properties. This study aims to improve the prediction of the mechanical properties of CNT-reinforced cementitious materials, specifically, elastic modulus and flexural strength, by leveraging multiple predictive Artificial Intelligence (AI)-based models. Deep Neural Networks (DNN), ensemble-bagging, and Support Vector Regression (SVR) were proposed and rigorously tested to predict the flexural strength and elastic modulus of the composite material. The feature selection was performed based on the domain knowledge and the informative metrics including the permutation importance analyses and Pearson's correlation analyses. The research identified several parameters that have traditionally been overlooked but proved to be critical. With a total of nineteen input parameters analyzed, the findings indicate that the mechanical properties of the composite material are primarily influenced by surfactant-to-CNT mass ratio, CNT content and physical properties, as well as ultrasonication process. Conversely, sand type and CNT purity are found to have minimal importance to the change in mechanical properties. In addition, the proposed DNN models outperform other ML models in predicting both flexural strength and elastic modulus, achieving R-squared values of 0.93 and 0.86 with mean absolute percentage errors of 8.16% and 7.22%, respectively.