Si Rajoy nagin man Ministro sa administrasyon ni Jose Aznar sa pag'ultan kan 1996 asin 2003, asin bise sa Primer Ministro sa pag'ultan kan 2000-2003. Siya man an lider kan Oposisyon sa tanga kan 2004 asin 2011 sa lindong kan gobyerno ni Jose Zapatero.