Embedded cluster models of the (001) terrace site have been used to determine adsorption structures and energetics for NOx (NO2, NO3) SOx (SO2, SO3), as well as for CO2 on the entire sequence (MgO-BaO) of alkaline-earth-metal oxides. The calculations have been performed at the gradient-corrected density functional level. The oxidation of NO, NO2, SO2, and CO using surface peroxo species is also considered with the aim of contributing to the understanding of car emission control catalysts based on the NOx storage and reduction concept. For all substrates, the stability of the formed surface species is in the order NO2- approximate to CO32- < NO3- < SO42-. Between substrates the stability of the adsorbates is determined by the substrate basicity, which in turn is regulated by the lattice parameter. The resulting order is MgO < CaO < SrO < BaO. Several different bonding modes and structures are found, which differ in terms of degree of charge transfer from the substrate and how the resulting charge deficiency in the substrate is distributed among the surface ions.