We present a combined experimental and theoretical analysis of the atomic structure and the magnetic properties of 1- and 2-monolayer (ML)thick Co films on Pd(001) grown by thermal deposition (TD) and pulsed laser deposition (PLD). While surface X-ray diffraction measurements show that the geometric structures of the as-deposited samples differ depending on the deposition method (alloy formation for PLD versus epitaxial growth for TD), magneto-optic Kerr-effect loops indicate an in-plane easy magnetization axis independent of the preparation method. Annealing at 600 K induces a reorientation of the easy magnetization axis from in-plane to out of plane. This goes in parallel with substantial structural reorganization, leading to a Co/Pd multilayer structure with a top Pd layer. In agreement with experiments, fully relativistic Kohn-Korringa-Rostoker calculations including experimentally derived structural relaxations and disorder predict in-plane magnetization for the as-grown samples and out-of-plane magnetization for the annealed 2 ML sample characterized by an (incomplete) Pd/Co/Pd/Co/Pd(001)layer sequence. However, in-plane magnetization for the 1 ML Pd/Co/Pd(001) sandwich is theoretically predicted. Our study emphasizes the decisive importance of structural order, relaxation, and interface contribution to the magnetic anisotropy energy.