15 grudnia 2001 został przewodniczącym Bułgarskiej Partii Socjalistycznej, w tym samym miesiącu stanął na czele klubu parlamentarnego koalicji. Po zwycięstwie socjalistów w wyborach parlamentarnych w 2005 zadeklarował, że w nowym gabinecie nie znajdzie się miejsce dla przedstawicieli Narodowego Ruchu Symeona Drugiego, który rządził w latach 2001–2005. Jednak, kiedy 27 lipca jego propozycja gabinetu została odrzucona w parlamencie głosami m.in. liberałów, rozpoczęły się pierwsze próby zawiązania nowej koalicji. Ostatecznie, 16 sierpnia, Sergej Staniszew ogłosił nowy skład rządu, w którym zasiedli ministrowie trzech największych partii w Zgromadzeniu Narodowym 40. kadencji (oprócz socjalistów i partii jego poprzednika także Ruchu na rzecz Praw i Wolności).
Sergej Staniszew był trzecim w historii Bułgarii premierem, który przetrwał na swoim stanowisku pełną, czteroletnią kadencję. W okresie pełnienia przez niego tej funkcji Bułgaria weszła do Unii Europejskiej. Jego gabinet oskarżany był jednak o brak skuteczności w walce z korupcją, marnotrawienie funduszy unijnych oraz uzależnienie kraju od dostaw gazu z Rosji.