The Muon Ionization Cooling Experiment (MICE) will demonstrate the principle of muon beam phase-space reduction via ionization cooling. Muon beam cooling will be required for the proposed Neutrino Factory or Muon Collider. The phase-space before and after the cooling cell must be measured precisely. This is achieved using two scintillating-fibre trackers, each placed in a solenoidal magnetic field. This paper describes the software reconstruction for the fibre trackers: the GEANT4 based simulation; the implementation of the geometry; digitisation; space-point reconstruction; pattern recognition; and the final track fit based on a Kalman filter. The performance of the software is evaluated by means of Monte Carlo studies and the precision of the final track reconstruction is evaluated.