Sulfur and chlorine change the activity and selectivity of palladium-based hydrogenation catalysts, but the origins of these effects at the microscopic level remain elusive. The chemisorption of atomic sulfur and chlorine on small palladium clusters has been studied with the hybrid Hartree-Fock/density functional method (B3LYP functional). Full geometry optimizations have been performed, allowing the occurrence of low-symmetry structures, in order to investigate the size dependence of atomic adsorption geometry and energy. The latter properties vary in a monotonous way as the number of palladium atoms increase and seem to rapidly converge toward limiting values. Sulfur was found to adsorb on the higher coordination sites, with a Pd-S bond distance of 2.3 Angstrom, whereas chlorine prefers the 2-fold sites and the Pd-Cl bond is longer (2.5 Angstrom). An adsorption energy of about 25-30 kcal/mol per Pd-X bond was estimated for both atoms. The topological analysis of the electron localization function (ELF) revealed that the bond between sulfur or chlorine adatoms and palladium is not of the shared-electrons type.