In this study, the intelligent method of genetic programming (GP) was used for developing predictive models for estimating the frost layer thickness under natural and forced convection on ultra-low temperature surfaces. The affecting dimensionless parameters were used as GP input variables, and realistic empirical correlations were developed for estimating the frost thickness under different conditions. The coefficient of determination of 0.9731, 0.9812, and 0.9906, and average absolute relative error of 6.52%, 11.65%, and 2.87%, were obtained by the developed models for natural convection on vertical plates, natural convection on horizontal plates, and forced convection on horizontal plates, respectively. The physical trends of the developed models were evaluated by comparing the model predictions with the experimental data for different operating conditions, and reasonable agreements were obtained. The same experimental database was also compared to some existing correlations for ordinary-low temperature surfaces, but they failed to provide reasonable estimates for the data.