We report x-ray absorption spectroscopy and x-ray magnetic circular dichroism measurements as well as multiplet calculations for Dy, Ho, Er, and Tm atoms adsorbed on Pt(111), Cu(111), Ag(100), and Ag(111). In the gas phase, all four elements are divalent and we label their 4f occupancy as 4f(n). Upon surface adsorption, and depending on the substrate, the atoms either remain in that state or become trivalent with 4f(n-1) configuration. The trivalent state is realized when the sum of the atomic correction energies (4f -> 5d promotion energy E-fd + intershell coupling energy delta E-c) is low and the surface binding energy is large. The latter correlates with a high substrate density of states at the Fermi level. The magnetocrystalline anisotropy of trivalent RE atoms is larger than the one of divalent RE atoms. We ascribe this to the significantly smaller covalent radius of the trivalent state compared to the divalent one for a given RE element. For a given valency of the RE atom, the anisotropy is determined by the overlap between the spd states of the RE and the d states of the surface. For all investigated systems, the magnetization curves recorded at 2.5 K show absence of hysteresis indicating that magnetic relaxation is faster than about 10 s.