Politički angažman Šešelja tokom devedesetih godina odlikuje niz neizmeničnih perioda saradnje i razlaza sa režimom Slobodana Miloševića. Nekoliko puta su njihove stranke formirale takozvane „vlade narodnog jedinstva“ i vodile veoma složnu politiku u odnosu na konflikt u bivšoj Jugoslaviji. Sam Milošević nazvao je Šešelja kako svojim „omiljenim opozicionarom“ tako i „oličenjem nasilja i primitivizma“. Razilazili su se raznim povodima, ali uglavnom kada bi Šešeljeva stranka dovoljno ojačala, a Milošević popuštao pred zahtevima međunarodne zajednice, kao što je bio slučaj sa fijaskom Vens-Ovenovog plana 1993. (i potonjom blokadom Republike Srpske od strane beogradskog režima) i Kumanovskim sporazumom 1999. Po potpisivanju Dejtonskog sporazuma 1995, Slobodana Miloševića je nazvao „najvećim izdajnikom srpskog naroda“[8]. U periodima razilaženja, Šešeljeva SRS bi oštro kritikovala vladajući režim, sam Šešelj bi publikovao dela pod pitoresknim nazivima poput „Tiranin sa Dedinja“ (odnosi se na Slobodana Miloševića) ili „Narkomanija Vuka Manitoga“ (u vreme kada je SPS u Saveznoj vladi sarađivao sa SPO Vuka Draškovića umesto sa njegovom SRS), za Miloševiću suprugu prof. Mirjanu Marković govorio da je „crvena veštica sa Dedinja, nova prokleta Jerina i najveće zlo srpskog naroda“ [15], njegova partija bila izložena jednakom progonu državnih medija kao i ostale opozicione partije, pa bi čak dolazilo i do pokušaja saradnje među njima kao na primer pri konstituisanju Narodne Skupštine posle izbora 1993.
U zatvoru po treći put boravi od 29. septembra 1994. godine do 29. septembra 1995. godine. Iste godine, takođe zbog suprotstavljanja politici aktuelnog režima, boravi još 60 dana u zatvoru.
Pobedom SRS na lokalnim izborima 1996. u Zemunu (sam Šešelj živeo je u Batajnici), postaje predsednik Skupštine Opštine Zemun. U posetu Srbiji dovodi Žan-Mari Le Pena i Vladimira Žirinovskog.
Na izborima za predsednika Srbije održanim 21. septembra 1997. godine, Vojislav Šešelj osvojio je 1.125.140 glasova i ušao u drugi izborni krug. Sa 50,61% važećih glasačkih listića pobedio je protivkandidata Zorana Lilića, tada predsednika SRJ, ali su izbori ponovljeni nakon što je Republička izborna komisija objavila da je izlaznost bila 48,88%. Na ponovljenim izborima SPS kandiduje Milana Milutinovića, tadašnjeg ministra inostranih poslova SRJ, koji Šešelja pobeđuje u drugom krugu. Kao i većina ostalih zvaničnih rezultata izbora iz ovog perioda, i ovi ostaju kontraverzni, uz široko verovanje da su falsifikovani na Šešeljevu štetu[traži se izvor od 09. 2009.]. Na primer, u Drenici na Kosovu i Metohiji, utvrđenju albanskih separatista, zvanični rezultati pokazuju 90% upisanih birača za Milutinovića. Na oba ova izbora za predsednika Srbije učestvuje kao trećeplasirani u prvom krugu i Vuk Drašković; ostale opozicione stranke su ih, uglavnom neuspešno, bojkotovale.
Šešelj postaje zatim potpredsednik Vlade Republike Srbije u kabinetu Mirka Marjanovića 1998–2000. Pozicija Srbije na početku mandata ove Vlade bila je teška, a na njenom isteku i neuporedivo gora. Odnosi sa Vladom u Crnoj Gori su krajnje zaoštreni što je u krajnjem rezultiralo ukidanjem SRJ 2003, a oružana pobuna na Kosovu i Metohiji eskalirala je u oštar rat koji se, nakon referenduma na kojem je odbijeno učešće međunarodnih pregovarača, snažnih spoljnih pritisaka, i kraha pregovora u Rambujeu, završio agresijom NATO pakta u proleće 1999.
Agresija je zaustavljena potpisivanjem Kumanovskog sporazuma koji je uspostavio protektorat Ujedinjenih nacija i de fakto suspendovao svaki suverenitet Srbije u toj pokrajini; Šešelj i ostali članovi Vlade iz redova Srpske radikalne stranke su se usprotivili potpisivanju ovog sporazuma i podneli ostavke na članstvo u Vladi ali su potom nastavili da obavljaju svoje dužnosti, obrazlažući to nacionalnim interesima. Na unutrašnje-političkom planu ova Vlada u kojoj je Šešelj igrao važnu ulogu ostala je zapamćena pre svega po donošenju kontroverznih zakona o informisanju i o univerzitetima. Primena zakona o informisanju rezultirala je neviđenim pritiskom na novinare čije se izveštavanje nije uklapalo u okvire koje je propisala Vlada (tzv. „nezavisni novinari“); sudskim procesima po tužbama uglavnom nepoznatih građana i organizacija (npr. „Patriotskog saveza Jugoslavije“) koji su rešavani u roku od 24 časa izuzetno visokim novčnim kaznama; zabranama i zatvaranjem nekoliko dnevnika, nedeljnih novina i radio-stanica; te progonima pa i ubistvima nekoliko novinara. Zakon o univerzitetu suspendovao je autonomiju („samoupravljanje“ kako je to objašnjavala Vlada) visokog školstva i omogućio Vladi postavljenje dekana i rektora i gotovo potpunu kontrolu nad zbivanjima na Univerzitetima čiji je osnivač; što je dovelo do revolta i ostavki od strane određenog broja univerzitetskih profesora. U ovom periodu Šešelj bio je izabran i za redovnog profesora na Pravnom Fakultetu u Beogradu.
Jedino,sto je bio pragma pa je znao da izvaga sta ce manje da nas kosta...
narodno veselje koje na žalost mi placamo
