One of the most interesting phenomena in solid-state physics is Anderson localization, which predicts that an electron may become immobile when placed in a disordered lattice. The origin of localization is interference between multiple scatterings of the electron by random defects in the potential, altering the eigenmodes from being extended (Bloch waves) to exponentially localized. As a result, the material is transformed from a conductor to an insulator. Anderson's work dates back to 1958, yet strong localization has never been observed in atomic crystals, because localization occurs only if the potential (the periodic lattice and the fluctuations superimposed on it) is time-independent. However, in atomic crystals important deviations from the Anderson model always occur, because of thermally excited phonons and electron-electron interactions. Realizing that Anderson localization is a wave phenomenon relying on interference, these concepts were extended to optics. Indeed, both weak and strong localization effects were experimentally demonstrated, traditionally by studying the transmission properties of randomly distributed optical scatterers (typically suspensions or powders of dielectric materials). However, in these studies the potential was fully random, rather than being 'frozen' fluctuations on a periodic potential, as the Anderson model assumes. Here we report the experimental observation of Anderson localization in a perturbed periodic potential: the transverse localization of light caused by random fluctuations on a two-dimensional photonic lattice. We demonstrate how ballistic transport becomes diffusive in the presence of disorder, and that crossover to Anderson localization occurs at a higher level of disorder. Finally, we study how nonlinearities affect Anderson localization. As Anderson localization is a universal phenomenon, the ideas presented here could also be implemented in other systems (for example, matter waves), thereby making it feasible to explore experimentally long-sought fundamental concepts, and bringing up a variety of intriguing questions related to the interplay between disorder and nonlinearity.