Magnetic phenomena are ubiquitous in our surroundings and indispensable for modern science and technology, but it is notoriously difficult to change the magnetic order of a material in a rapid way. However, if a thin nickel film is subjected to ultrashort laser pulses, it can lose its magnetic order almost completely within merely femtosecond times. This phenomenon, in the meantime also observed in many other materials, has connected magnetism with femtosecond optics in an efficient, ultrafast and complex way, offering opportunities for rapid information processing or ultrafast spintronics at frequencies approaching those of light. Consequently, the physics of ultrafast demagnetization is central to modern material research, but a crucial question has remained elusive: If a material loses its magnetization within only femtoseconds, where is the missing angular momentum in such short time? Here we use ultrafast electron diffraction to reveal in nickel an almost instantaneous, long-lasting, non-equilibrium population of anisotropic high-frequency phonons that appear as quickly as the magnetic order is lost. The anisotropy plane is perpendicular to the direction of the initial magnetization and the atomic oscillation amplitude is 2 pm. We explain these observations by means of circularly polarized phonons that quickly absorb the missing angular momentum of the spin system before the slower onset of a macroscopic sample rotation. The time that is needed for demagnetization is related to the time it takes to accelerate the atoms. These results provide an atomistic picture of ultrafast demagnetization under adherence to all conservation laws but also demonstrate the general importance of polarized phonons for non-equilibrium dynamics and provide innovative ways for controlling materials on atomic dimensions.