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. After deposition corresponding to a 200 nm thick (Ga,Mn)As layer the nanowires are around 700 nm long. Their shapes are tapered, with typical diameters around 30 nm at the base and 7 nm at the tip. The wires grow along the 111 direction, i.e., along the surface normal on GaAs(111)B and inclined on GaAs(001). In the latter case they tend to form branches. 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.