The aeronautical industry is still under expansion in spite of the problems it is facing due to the increase in oil prices, limited capacity, and novel regulations. The expansion trends translate into problems at different locations within an airport system and are more evident when the resources to cope with the demand are limited or are reaching to theirs limits. In the check-in areas they are appreciated as excessive waiting times which in turn are appreciated by the customers as bad service levels. The article presents a novel methodology that combines an evolutionary algorithm and simulation in order to give the best results taking into account not only the mandatory hard and soft rules determined by the internal policies of an airport terminal but also the quality indicators which are very difficult to include using an abstract representation. The evolutionary algorithm is developed to satisfy the different mandatory restrictions for the allocation problem such as minimum and maximum number of check-in desks per flight, load balance in the check-in islands, opening times of check-in desks and other restrictions imposed by the level of service agreement. Once the solutions are obtained, a second evaluation is performed using a simulation model of the terminal that takes into account the stochastic aspects of the problem such as arriving profiles of the passengers, opening times physical configurations of the facility among other with the objective to determine which allocation is the most efficient in real situations in order to maintain the quality indicators at the desired level.