We have investigated magnetic properties of atomic wires of Ga-substituted Mn on the GaAs(110) surface using first-principles calculations based on the spin-density functional theory. Mn atomic wires are assumed to align along the <110>-, <001>-, and <211>-directions. The <110>-oriented wire is most stable energitically, and has the ferromagnetic ground state with the magnetic moment of 4.0 μ_B per Mn atom. The band structure has a large dispersion along the wire and exhibits a half-metallic state. The ferromagnetic character of the Mn wire results from the double exchange interaction through the p-d hybridization between the Mn-3d and the GaAs surface states.