We show that stable skyrmions with diameters of a few nanometers can emerge in atomic Pd/Fe bilayers on the Rh(111) surface. Based on density functional theory we calculate the exchange and the Dzyaloshinskii-Moriya interaction as well as the magnetocrystalline anisotropy energy. The latter two terms are driven by spin-orbit coupling and significantly reduced compared to Pd/Fe bilayers on Ir(111) as expected since Rh and Ir are isoelectronic 4d and 5d transition metals. However, there is still a spin spiral ground state at zero magnetic field. Atomistic spin dynamics simulations show that a skyrmion phase occurs at small magnetic fields of ∼1 T. Skyrmion diameters amount to 2-8 nm and skyrmion lifetimes are up to 1 h at temperatures of 25-45 K.