W 1989 został sekretarzem do spraw przemysłu, energetyki i inżynierii w administracji Serbii. W 1991 objął stanowisko ministra górnictwa i energii, później w tym samym roku powołany dodatkowo na wicepremiera serbskiego rządu. W 1992 został ministrem gospodarki. W lutym 1993 mianowany premierem Serbii, urząd ten sprawował do marca 1994. Przeszedł wówczas na stanowisko wicepremiera Federalnej Republiki Jugosławii, które zajmował do 2000. Był również deputowanym do federalnego parlamentu.
Należał do najbliższych współpracowników Slobodana Miloševicia. W 1998 został przez niego wyznaczony na specjalnego przedstawiciela w Kosowie, w którym trwała wówczas wojna domowa. Prowadzonego przez niego negocjacje z Albańczykami zakończyły się niepowodzeniem.
Od 1999 Międzynarodowy Trybunał Karny dla byłej Jugosławii prowadził wobec niego postępowanie w sprawie terroru i przemocy wobec kosowskich Albańczyków. W maju 2002 Nikola Šainović, nieprzyznający się do popełnienia zarzucanych mu zbrodni, dobrowolnie poddał się, po czym został przekazany do Hagi. Jako tymczasowo aresztowany oczekiwał na proces, który rozpoczął się w 2006. W 2009 w pierwszej instancji został uznany za winnego zbrodni przeciwko ludzkości i zbrodni wojennych (w tym deportacji i zabójstw) oraz skazany przez ICTY na karę 22 lat pozbawienia wolności.