In forecasting, evolutionary algorithms are often linked to existing forecasting methods to optimize their input parameters. Traditionally, the fitness function of these search heuristics is based on an accuracy measure. In this paper, however, we combine forecasting accuracy with business expertise by defining a flexible and easily interpretable profit function for sales forecasting, which is based on the profit margin of a given product, the volume of its sales and the accuracy of the forecast. ProfARIMA is a new procedure that selects the lags of a Seasonal ARIMA model according to the profit of a model's forecasts by taking advantage of search heuristics. This procedure is tested on both publicly available datasets and a real-life application with datasets of The Coca-Cola Company in order to assess its performance, both in profit and accuracy. Three different evolutionary algorithms were implemented during this testing process, i.e. Genetic Algorithms, Particle Swarm Optimization and Simulated Annealing. The results indicate that ProfARIMA always performs at least equally to the Box–Jenkins methodology and often outperforms this traditional procedure. For The Coca-Cola Company, our new algorithm in combination with Genetic Algorithms even leads to a significantly larger profit for out-of-sample forecasts.