GaAs:Mn nanowires were obtained on GaAs(001) and GaAs(111)B substrates by molecular beam epitaxial growth of (Ga,Mn)As at conditions leading to MnAs phase separation. Their density is proportional to the density of catalyzing MnAs nanoislands, which can be controlled by the Mn flux and/or the substrate temperature. Being rooted in the ferromagnetic semiconductor (Ga,Mn)As, the nanowires combine one-dimensional properties with the magnetic properties of (Ga,Mn)As and provide natural, self assembled structures for nanospintronics.