Met Frits Bolkestein als partijleider zorgde de VVD in de jaren negentig op electoraal terrein en wat betreft de partijen waarmee zij zou gaan regeren, voor grote verrassingen. Bij de Tweede Kamerverkiezingen wist de nieuwe lijsttrekker de neergang om te buigen in groei: 31 zetels in 1994 – het een-na-beste resultaat ooit – en 38 in 1998, een record. Dat Bolkestein het electoraal zo goed zou doen kwam toch wel wat onverwacht: charismatisch was hij niet, en met zijn geaffecteerde taalgebruik en intellectualistische uitstraling leek het voor hem niet eenvoudig lager opgeleide kiezers te bereiken. Met zijn aanvallen op enkele taboes in de Nederlandse politiek, zoals de hoogte van het bedrag voor de ontwikkelingssamenwerking, de als positief beschouwde Europese samenwerking en problemen rond migratie en integratie ontwikkelde Bolkestein zich evenwel tot ‘spreekbuis van de conservatief ingestelde gewone man’, wat mede zijn electorale triomfen verklaart.
Ook de Europese verkiezingen op 9 juni 1994 verliepen voor de VVD zeer succesvol. Het aantal liberale zetels verdubbelde – mede omdat Nederland meer zetels in het Europees Parlement kreeg – en kwam uit op zes. Lijsttrekker Gijs de Vries werd tot voorzitter gekozen van de Liberale en Democratische fractie (ELDR) van het Europees Parlement.
Na de Kamerverkiezingen van 1994 vormde de VVD met D66 en de PvdA de zogeheten ‘paarse’ coalitie. Voor het eerst sinds 1952 regeerde zij weer samen met de sociaaldemocraten. In de verkiezingscampagne , maar ook daarvoor en daarna, was de PvdA altijd het doelwit geweest van de VVD-leiders; met name Pieter Oud en Hans Wiegel hadden de sociaaldemocraten verketterd. Het eerste kabinet-Kok, zoals de regeringscombinatie officieel heette, kwam echter niet uit de lucht vallen. In het Haagse hotel Des Indes praatten meer of minder prominente partijleden al sinds 1976 over mogelijke samenwerking. Belangrijker waren de negatieve ervaringen van de VVD met het CDA in het eerste twee kabinetten-Lubbers (1982-1989). Een partijcommissie onder leiding van Hans Nord noemde in 1990 het feit dat het CDA naar believen kon uitmaken met welke partij het wenste te regeren een ‘ongezonde toestand’. Deze opvatting vond tijdens de behandeling van het rapport op de algemene vergadering in april 1991 veel weerklank. Daarmee ging de deur naar een coalitie met de PvdA op een kier. Henk Vonhoff, Commissaris der Koningin in Groningen, noemde de toenadering tot de sociaaldemocraten ingrijpend. Bolkestein stelde dat ‘het vroegtijdig uitspreken van een voorkeur of een veto over een toekomstige coalitiegenoot politiek niet raadzaam is'. Vanaf 1991 troffen prominente PvdA’ers en VVD’ers elkaar bij vice-fractievoorzitter Hans Dijkstal thuis, in Wassenaar.
Zo maakten voor het eerst sinds 1918 de confessionele dan wel christendemocratische partijen geen deel uit van de regering. Bolkestein trad niet toe tot het kabinet. Hij wilde als partijleider in de Tweede Kamer blijven, want hij achtte het risico te groot dat de VVD als kleinere partner aan identiteit zou inboeten. Op deze wijze verwierf hij zich ook grotere ruimte voor zijn dissidente ideeën. Met opmerkelijke uitspraken, die zich regelmatig tegen het kabinetsbeleid richtten, haalde hij veelvuldig het nieuws, wat de VVD electoraal geen windeieren legde. Na de Tweede Kamerverkiezingen van 1998 zetten de liberalen de samenwerking met PvdA en D66 in Paars voort; Bolkestein maakte als partijleider plaats voor Dijkstal.
