Na de Tweede Kamerverkiezingen van 1998 was Hans Dijkstal Frits Bolkestein als partijleider opgevolgd. Hij bleef buiten het tweede kabinet-Kok van PvdA, VVD en D66. In mei 1999 leidde de stem van het Eerste Kamerlid Hans Wiegel tegen de invoering van het correctief referendum tot een kabinetscrisis. D66 wilde afhaken, maar ging uiteindelijk akkoord met onder meer de invoering van een niet-bindend (raadgevend) referendum. Het tweede kabinet-Kok kwam in april 2002 ten val, vlak voor de Tweede Kamerverkiezingen. De aanleiding vormde een rapport over de moord van 7000 Bosnische mannen door Servische troepen in Srebrenica in 1995 en de rol van de Nederlandse VN-militairen.
Bij de verkiezingen voor de Provinciale Staten op 3 maart 1999 viel de VVD wat terug, wat niet zo vreemd was gezien het grote succes in 1995. In juni boekte zij bij de Europese verkiezingen juist weer enige winst. Bij de Tweede Kamerverkiezingen op 6 mei 2002 maakte partijleider Dijkstal zijn debuut als lijsttrekker. In het voorjaar van 2001 had de VVD in de opiniepeilingen op 44 zetels gestaan, maar in de herfst zakte de partij terug door de opkomst van Pim Fortuyn. In de verkiezingscampagne maakte Dijkstal een matte en weinig geïnspireerde indruk, vooral in de debatten met Fortuyn. De VVD had bij de gemeenteraadsverkiezingen op 6 maart al fors verloren en raakte op 15 mei 2002 bij de Tweede Kamerverkiezingen veertien van haar 38 zetels kwijt – vooral aan de Lijst Pim Fortuyn (LPF).
Dijkstal werd als fractievoorzitter opgevolgd door Gerrit Zalm. Hoewel de VVD als één van de grote verliezers van de Kamerverkiezingen niet stond te trappelen om weer te gaan meeregeren, trad zij uiteindelijk toch toe tot de coalitie met CDA en LPF. Door de grote politieke onervarenheid van de LPF en zijn bewindslieden kwam dit eerste kabinet-Balkenende al in oktober 2002 ten val. Zalm werd door de LPF verweten dat hij ‘de stekker eruit had getrokken’.
Bij de vervroegde Tweede Kamerverkiezingen van 22 januari 2003 wist de VVD onder leiding van Zalm vier zetels terug te winnen (voornamelijk ten koste van de LPF). Van een electorale opleving was geen sprake, aangezien de liberalen bij de Provinciale Statenverkiezingen op 11 maart 2003 en bij de Europese verkiezingen op 10 juni 2004 fors verloren.
Met de voortgezette electorale teruggang betaalde de VVD wellicht een prijs voor deelname aan het tweede kabinet-Balkenende, waarin ook CDA en D66 zitting hadden. Zalm was hiervan vicepremier en minister van Financiën. Het kabinet kwam in juni 2006 ten val, nadat de Tweede Kamerfractie van D66 haar vertrouwen opzegde in minister Rita Verdonk voor Vreemdelingenbeleid en Integratie. Aanleiding was het optreden van Verdonk ten aanzien van het in Somalië geboren Tweede Kamerlid Ayaan Hirsi Ali, die behoorde tot de VVD-fractie, vanwege de wijze waarop zij de Nederlandse nationaliteit had verkregen. Nadat de D66-bewindspersonen waren opgestapt vormden CDA en VVD het derde kabinet-Balkenende, dat de vervroegde Tweede Kamerverkiezingen moest voorbereiden. Deze zouden op 22 november 2006 worden gehouden. In de peilingen stond de VVD op aanzienlijk verlies: het was na de eeuwwisseling duidelijk geworden dat de electorale hoogtijperiode onder Bolkestein was afgelopen.
