We developed a fast and robust algorithm to register intraoperative three-dimensional ultrasound data of the spine with preoperative CT data. We compared different gradient-based and evolutionary optimization strategies for solving the registration problem. The iRprop, a fast gradient-based optimization algorithm, quickly and reliably led to higher registration rates than the two established methods BFGS and conjugate gradient descent (CG). The Covariance Matrix Adaptation evolution strategy (CMA) yielded the best results concerning registration rate and accuracy but at the cost of a slightly higher number of evaluations of the optimization criterion compared to CG and iRprop. The CMA was able to register patient data starting from a realistic misalignment in 98% of the trials in about 15 s per registration.