Το 2004, παραιτήθηκε από την προεδρική αναμέτρηση για να κάνει χώρο για τον τρέχοντα αρχηγό κράτους, Τραϊάν Μπασέσκου.
Stolojan'ın bu hareketi, şaşırtıcı olsa da eşi görülmemiş değildi. 2004 yılında da görevdeki devlet başkanı Traian Basescu'ya yer açmak için kendisi cumhurbaşkanlığı yarışından çekilmişti.