Over the last few decades, researchers have focused on developing models that aim to predict the drillability of natural stones based on their physicomechanical properties using regression analyses. This study aims to investigate the relationships between the drilling rate index (DRI) of natural stones and their mineralogical and textural properties. A database composed of 37 natural stone samples was used to develop new DRI estimation models using regression analysis and the application of an evolutionary algorithm. The results revealed that the DRI could be predicted based on the texture coefficient, Shore scleroscope hardness, and the product of the uniaxial compressive strength and Brazilian tensile strength based on an analysis of the combined dataset consisting of natural stones of metamorphic, sedimentary, and magmatic origins. The non-linear models developed by the evolutionary computation algorithm revealed that the texture coefficient, mean grain size, uniaxial compressive strength, and Brazilian tensile strength could be used to predict the DRI of metamorphic natural stones. This study differs from previous studies through its use of a novel evolutionary algorithm based on a combination of gene expression programming and particle swarm optimization, which was used to perform a non-linear regression analysis to identify models that could accurately predict DRI. To improve the generalizability of the proposed models, more types of natural stones, especially those with magmatic origins, should be included in the database analyzed in this study.