The relativistic nuclear recoil corrections to the energy levels of low-lying states of hydrogenlike and high-Z lithiumlike atoms in all orders in αZ are calculated. The calculations are carried out using the B-spline method for the Dirac equation. For low Z the results of the calculation are in good agreement with the αZ-expansion results. It is found that the nuclear recoil contribution, in addition to Salpeter's contribution, to the Lamb shift (n=2) of hydrogen is -1.32(6) kHz. The total nuclear recoil correction to the energy of the (1s)2p1/2-(1s)22s transition in lithiumlike uranium constitutes -0.07 eV and is largely made up of QED contributions.