Many-body systems at low temperatures generally organize themselves into ordered phases, whose nature and symmetries are captured by an order parameter. This order parameter is spatially uniform in the simplest cases, for example the macroscopic magnetization of a ferromagnetic material. Non-uniform situations also exist in nature, for instance in antiferromagnetic materials, where the magnetization alternates in space, or in the so-called stripe phases emerging for itinerant electrons in strongly correlated materials. Understanding such inhomogeneously ordered states is of central importance in many-body physics. Here we study experimentally the magnetic ordering of itinerant spin-1 bosons in inhomegeneous spin domains at nano-Kelvin temperatures. We demonstrate that spin domains form spontaneously, that is purely because of the antiferromagnetic interactions between the atoms and in the absence of external magnetic forces, after a phase separation transition. Furthermore, we explore how the equilibrium domain configuration emerges from an initial state prepared far from equilibrium.