Emulation plays an indispensable role in engineering design. However, the majority of emulation methods are formulated for interpolation purposes and their performance significantly deteriorates in extrapolation. In this paper, we develop a method for extrapolation by integrating Gaussian processes (GPs) and evolutionary programming (EP). Our underlying assumption is that there is a set of free-form parametric bases that can model the data source reasonably well. Consequently, if we can find these bases via some training data over a region, we can do predictions outside of that region. To systematically and efficiently find these bases, we start by learning a GP without any parametric mean function. Then, a rich dataset is generated by this GP and subsequently used in EP to find some parametric bases. Afterwards, we retrain the GP while using the bases found by EP. This retraining essentially allows to validate and/or correct the discovered bases via maximum likelihood estimation. By iterating between GP and EP we robustly and efficiently find the underlying bases that can be used for extrapolation. We validate our approach with a host of analytical problems in the absence or presence of noise. We also study an engineering example on finding the constitutive law of a composite microstructure.