The mechanical features of concrete made with multiple quantities of recycled coarse aggregate replacing natural gravel were investigated in this work. In addition, behavior variations of concrete specimens with recycled and natural coarse aggregates after incorporating colloidal nano-silica were addressed. For this purpose, 13 experimental groups and 195 specimens with different recycled coarse aggregate contents (0, 25, 50, 75, and 100%) and nano-silica (0, 1.5, 3, 4.5, and 6%) were produced. Then, key parameters including the compressive, splitting tensile, and flexural strengths, as well as ultrasonic pulse velocity (UPV), modulus of elasticity, water absorption, and porosity, were explored. Moreover, the test results were employed to propose empirical equations for the mechanical parameters of concrete with the recycled coarse aggregate and nano-silica contents as variables. The findings demonstrated a decline in the durability and mechanical characteristics by raising the quantity of recycled coarse aggregate replacing natural gravel. Furthermore, incorporating nano-silica in specimens containing recycled and those containing natural aggregate enhanced durability and mechanical features. Additionally, to determine the optimum values of the design variables to maximize the mechanical features and durability of concrete incorporating recycled coarse aggregate and nano-silica, the response surface method (RSM) was used; optimum quantities of nano-silica and recycled coarse aggregate were determined as 4 and 26%, respectively. Finally, gene expression programming (GEP) was used to predict the compressive capacity of concretes incorporating recycled coarse aggregate and nano-silica pozzolan. The model was developed using 168 concrete specimens extracted from the literature and showed a good correlation between the results.