In the Kondo effect, a localized magnetic moment is screened by forming a correlated electron system with the surrounding conduction electrons of a non-magnetic host. Spin S=1/2 Kondo systems have been investigated extensively in theory and experiments, but magnetic atoms often have a larger spin. Larger spins are subject to the influence of magnetocrystalline anisotropy, which describes the dependence of the magnetic moment's energy on the orientation of the spin relative to its surrounding atomic environment. Here we demonstrate the decisive role of magnetic anisotropy in the physics of Kondo screening. A scanning tunnelling microscope is used to simultaneously determine the magnitude of the spin, the magnetic anisotropy and the Kondo properties of individual magnetic atoms on a surface. We find that a Kondo resonance emerges for large-spin atoms only when the magnetic anisotropy creates degenerate ground-state levels that are connected by the spin flip of a screening electron. The magnetic anisotropy also determines how the Kondo resonance evolves in a magnetic field: the resonance peak splits at rates that are strongly direction dependent. These rates are well described by the energies of the underlying unscreened spin states.