Accurate and reliable registration of longitudinal spine images is essential for assessment of disease progression and surgical outcome. Implementing a fully automatic and robust registration for clinical use, however, is challenging since standard registration techniques often fail due to poor initial alignment. The main causes of registration failure are the small overlap between scans which focus on different parts of the spine and/or substantial change in shape (e.g. after correction of abnormal curvature) and appearance (e.g. due to surgical implants). To overcome these issues we propose a registration approach which incorporates estimates of vertebrae locations obtained from a learning-based classification method. These location priors are used to initialize the registration and to provide semantic information within the optimization process. Quantitative evaluation on a database of 93 patients with a total of 276 registrations on longitudinal spine CT demonstrate that our registration method significantly reduces the number of failure cases.