We describe a muon track reconstruction algorithm for the reactor anti-neutrino experiment Double Chooz. The Double Chooz detector consists of two optically isolated volumes of liquid scintillator viewed by PMTs, and an Outer Veto above these made of crossed scintillator strips. Muons are reconstructed by their Outer Veto hit positions along with timing information from the other two detector volumes. All muons are fit under the hypothesis that they are through-going and ultrarelativistic. If the energy depositions suggest that the muon may have stopped, the reconstruction fits also for this hypothesis and chooses between the two via the relative goodness-of-fit. In the ideal case of a through-going muon intersecting the center of the detector, the resolution is ~40 mm in each transverse dimension. High quality muon reconstruction is an important tool for reducing the impact of the cosmogenic isotope background in Double Chooz.