We report on highly Mn-doped GaAs nanowires (NWs) of high crystalline quality fabricated by ion beam implantation, a technique that allows doping concentrations beyond the equilibrium solubility limit. We studied two approaches for the preparation of Mn-doped GaAs NWs: First, ion implantation at room temperature with subsequent annealing resulted in polycrystalline NWs and phase segregation of MnAs and GaAs. The second approach was ion implantation at elevated temperatures. In this case, the single-crystallinity of the GaAs NWs was maintained, and crystalline, highly Mn-doped GaAs NWs were obtained. The electrical resistance of such NWs dropped with increasing temperature (activation energy about 70 meV). Corresponding magnetoresistance measurements showed a decrease at low temperatures, indicating paramagnetism. Our findings suggest possibilities for future applications where dense arrays of GaMnAs nanowires may be used as a new kind of magnetic material system.