A fully atomic orbital (AO)-based reformulation of second-order Møller-Plesset perturbation theory (MP2) energy gradients is introduced, which provides the basis for reducing the computational scaling with the molecular size from the fifth power to linear. Our formulation avoids any transformation between the AO and the molecular orbital (MO) basis and employs pseudodensity matrices similar to the AO-MP2 energy expressions within the Laplace scheme for energies. The explicit computation of perturbed one-particle density matrices emerging in the new AO-based gradient expression is avoided by reformulating the Z-vector method of Handy and Schaefer [J. Chem. Phys. 81, 5031 (1984)] within a density matrix-based scheme.