We presented a set of methods for registration of preoperative CT data set to intra-operative X-ray images in minimally invasive image-guided spinal surgery. The registration procedure is composed of two steps. Firstly, a rough registration using a variant form of Iterative Closest Point algorithm is adopted to get an overlapped area. Secondly, the fine registration is performed based on gradient projection features. In this step, we introduce a similarity measure of CT gradient projections and use genetic algorithm combined with Powell’s maximization method as optimization strategy, which is able to increase the precision of the registration. The successive registration rate achieves 92% and 81% respectively on simulation data and clinical phantom research. The experimental results show that proposed method is suitable for clinical application with good robustness.