A description is provided of the software algorithms developed for the CMS tracker both for reconstructing charged-particle trajectories in proton-proton interactions and for using the resulting tracks to estimate the positions of the LHC luminous region and individual primaryinteraction vertices. Despite the very hostile environment at the LHC, the performance obtained with these algorithms is found to be excellent. For tt events under typical 2011 pileup conditions, the average track-reconstruction efficiency for promptly-produced charged particles with transverse momenta of pT > 0:9GeV is 94% for pseudorapidities of jhj < 0:9 and 85% for 0:9 < jhj < 2:5. The inefficiency is caused mainly by hadrons that undergo nuclear interaction...