Using spin-polarized scanning tunneling microscopy we show that the magnetic order of 1 monolayer Mn on W(001) is a spin spiral propagating along 110 crystallographic directions. The spiral arises on the atomic scale with a period of about 2.2 nm, equivalent to only 10 atomic rows. Ab initio calculations identify the spin spiral as a left-handed cycloid stabilized by the Dzyaloshinskii-Moriya interaction, imposed by spin-orbit coupling, in the presence of softened ferromagnetic exchange coupling. Monte Carlo simulations explain the formation of a nanoscale labyrinth pattern, originating from the coexistence of the two possible rotational domains, that is intrinsic to the system.