Traditionally, univariate time-series models have largely dominated forecasting for international tourism demand. In this paper, the ability of a Genetic Programming (GP) to predict monthly tourist arrivals from UK and Germany to Balearic Islands (Spain) is explored. GP has already been employed satisfactorily in different scientific areas, but it is practically unknown into tourism forecasters. The technique shows different advantages regarding to other forecasting methods. Firstly, it does not assume a priori a rigid functional form of the model. Secondly, it is more robust and easy-to-use than other non-parametric methods. Finally, it provides explicitly a mathematical equation which allows a simple ad hoc interpretation of the results. Comparing the performance of the proposed technique against other method commonly used in tourism forecasting (No-change model, Moving average and ARIMA), the empirical results reveal that GP can be a valuable tool in this field.