За първи път той бе избран за премиер през 1992 г., когато президент на страната беше Киро Глигоров. Тогава Цървенковски бе на 29 години и стана най-младият правителствен ръководител в Европа по онова време.
Тој беше првиот избран премиер за време на претседателскиот мандат на Киро Глигоров во 1992 година, кога беше на 29-годишна возраст, со што стана најмлад шеф на влада во Европа во тоа време.