© 2015 IOP Publishing Ltd and Deutsche Physikalische Gesellschaft. We demonstrate single atom anisotropic magnetoresistance on the surface of a topological insulator, arising from the interplay between the helical spin-momentum-locked surface electronic structure and the hybridization of the magnetic adatom states. Our first-principles quantum transport calculations based on density functional theory for Mn on Bi2Se3 elucidate the underlying mechanism. We complement our findings with a two dimensional model valid for both single adatoms and magnetic clusters, which leads to a proposed device setup for experimental realization. Our results provide an explanation for the conflicting scattering experiments on magnetic adatoms on topological insulator surfaces, and reveal the real space spin texture around the magnetic impurity.