Passenger terminals are very complex buildings not only in their function, form and structure but also in infrastructure, security, comfort, energy, which deal with huge investments, both in terms of capital, as well as in terms of resources and environmental impact. As such, it is expected that they are designed to fulfill their purpose while minimizing their negative aspects to the environment. Identifying design solutions that satisfy these goals is a challenging task due to the complexity involved. The design task is characterized by excessive number of solutions, conflicting goals and complex relations between design decision variables, objectives and constraints. As such, appropriate, informed decisions, that integrate as many design aspects as possible, should be ensured as early as the conceptual stage of the design. In this study, the problem of conceptual airport terminal design is addressed by means of computational decision support methodologies. The proposed method is based on the integration of the following components: i. a parametric modeling approach, for enabling the instantaneous generation of a wide variety of designs, ii. a multi-faceted evaluation scheme, which integrates functional, energy and architectural aspects, iii. a Multi-Objective Genetic Algorithm, namely the NSGA-II, to identify well performing solutions. A computational model implementing the method is outlined, and validation of the method is performed, based on two different scenarios, corresponding to commonly occurring airport configurations. The performance of two optimization runs with different population sizes, as well as qualitative aspects of the resulting solutions is discussed.