Using a combination of analytic-potential and first-principles density functional theory (DFT) calculations, composition effects on energetics, adsorption energies, and catalytic activity of Au-Pd nanoalloys are investigated, selecting CO oxidation to CO2 as a prototypical reaction and 55-atom Au-Pd clusters with Mackay icosahedral structure as template systems. It is first shown that the Au54Pd1, Au43Pd12, Au42Pd13, and Au12Pd43 nanoalloys with highly symmetric structures are well separated from other nanoalloys due to their special relative stability at the empirical potential and/or DFT levels, with CO adsorption energies on top of Au atoms found to be weakly dependent on composition in a range around 50:50 Au:Pd ratio. The explicit calculation of reaction energy barriers for the CO oxidation process then shows that these are sensitive to the composition of nanoalloys, where Au-rich clusters possess a high catalytic activity and the Au43Pd12 cluster is predicted to have the highest catalytic activity among the clusters here considered. Our results highlight a non-monotonous behavior of the catalytic activities of Au-Pd nanoalloys on composition that is of fundamental interest for the design of new catalysts, but also the subtleties of a delicate interplay of structural and electronic effects in determining reaction energetics, which are difficult to summarize into few, simple prescriptions. (c) 2014 Elsevier Inc. All rights reserved.