The structure of Co-doped Pd-n (n = 1-12) clusters is investigated using density functional theory (DFT) global optimization based on simulated annealing. The earlier putative global minimum of Pd12Co is now confirmed to be an icosahedron (I-h) with the Co atom in the center site, while unexpectedly cage structures are found for Pd-9(-)11 Co clusters, which are different than the icosahedral fragments. The results show, that doping with a Co atom increases the stability of Pd-n clusters and enhances their magnetic moment in the range of 1-3 mu(B). Ferromagnetic (FM) ordering between the Co atom and the Pd-n host are energetically favored.