In real-world problems with candidate solutions that are very expensive to evaluate, Surrogate Models (SMs) mimic the behaviour of the simulation model as closely as possible while being computationally cheaper to evaluate. Due to their nature, SMs can be seen as heuristics that can help to estimate the fitness of a candidate solution without having to evaluate it. In this paper, we propose a new SM based on Genetic Programming (GP) and Radial Basis Function Networks (RBFN), called GP-RBFN Surrogate. More specifically, we use GP to evolve both: the structure of a RBF and its parameters. The SM evolved by our algorithm is tested in one of the most studied NP-complete problem (MAX-SAT) and its performance is compared against RBFN Surrogate, GAs, Random Search and (1+1) ES. The results obtained by performing extensive empirical experiments indicate that our proposed approach outperforms the other four methods in terms of finding better solutions without the need of evaluating a large portion of candidate solutions.