We prove Anderson localization at the internal band-edges for periodic magnetic Schr{o}dinger operators perturbed by random vector potentials of Anderson-type. This is achieved by combining new results on the Lifshitz tails behavior of the integrated density of states for random magnetic Schr{o}dinger operators, thereby providing the initial length-scale estimate, and a Wegner estimate, for such models.