Nanofluid (NF) pool boiling experiments have been conducted widely in the past two decades to study and understand how nanoparticles (NP) affect boiling heat transfer and critical heat flux (CHF). However, the physical mechanisms related to the improvements in CHF in NF pool boiling are still not conclusive due to the coupling effects of the surface characteristics and the complexity of the experimental data. In addition, the current models for pool boiling CHF prediction, which consider surface microstructure characteristics, show limited agreement with the experimental data and do not represent NF pool boiling CHF. In this scenario, artificial intelligence tools, such as machine learning (ML) regressor models, are a very promising means of solving this nonlinear problem. This study focuses on creating a new model to provide more accurate NF pool boiling CHF predictions based on pressure, substrate thermal effusivity, and NP size, concentration, and effusivity. Three ML models (supporting vector regressor—SVR, multi-layer perceptron—MLP, and random forest—RF) were constructed and showed good agreement with an experimental database built from the literature, with MLP presenting the highest mean R2 score and the lowest variability. A systematic methodology for optimizing the ML models is proposed in this work.