De periode 1998-2006 verliep electoraal gezien slecht voor D66. Van het recordaantal van 24 Kamerzetels die Hans van Mierlo in 1994 had behaald, was er volgens de peilingen in 2006 nog maar één over. Interne spanningen als gevolg van deelname aan het tweede kabinet-Balkenende droegen aan de neergang bij.
Bij de Tweede Kamerverkiezingen van 6 mei 1998 verloor D66 na deelname aan het eerste, ‘paarse’ kabinet-Kok tien zetels. PvdA en VVD wonnen, waardoor D66 niet meer nodig was voor de vorming van een tweede paarse regeringscoalitie. Partijleider Els Borst vond dat haar partij toch mee moest doen: ‘Kwantitatief zijn we misschien niet nodig, maar kwalitatief wel degelijk.’ D66 trad toe tot het tweede kabinet-Kok; Borst bleef minister van Volksgezondheid, Welzijn en Sport en werd vicepremier.
Op initiatief van D66 probeerde de paarse coalitie het correctief referendum in te voeren. Voor de vereiste grondwetswijziging was in tweede lezing een twee derde meerderheid in beide Kamers nodig. In mei 1999 stemde VVD-senator Hans Wiegel tegen, waardoor het wetsvoorstel in de Eerste Kamer sneuvelde. De D66-ministers besloten op te stappen, waarna premier Wim Kok het ontslag van het kabinet aanbood. D66 liet zich vervolgens lijmen, wat haar geloofwaardigheid niet ten goede kwam. 
Vervolgens hield de electorale neergang aan. Nadat het tweede kabinet-Kok was gevallen over de nasleep van de kwestie-Srebrenica, behaalde D66 bij de door Pim Fortuyn gedomineerde Tweede Kamerverkiezingen van 15 mei 2002 slechts zeven zetels. Fractievoorzitter Thom de Graaf, die lijsttrekker was geweest, stelde zijn positie ter beschikking maar werd door zijn fractie gevraagd om aan te blijven. Bij de vervroegde Tweede Kamerverkiezingen 22 januari 2003 mocht het ‘kleine’ D66 niet meer meedoen aan de belangrijkste tv- en radiodebatten. Na nieuw zetelverlies nam Boris Dittrich het fractievoorzitterschap over.
Onder Dittrich vormde D66 met CDA en VVD het tweede kabinet-Balkenende. Voor het eerst namen de Democraten deel aan een regering zonder de PvdA, wat intern tot weerstand leidde. Met de ministerpost ‘Bestuurlijke vernieuwing en Koninkrijkrelaties’ – ingenomen door De Graaf – zou D66 haar ‘kroonjuwelen’ als het gekozen burgemeesterschap en een nieuw kiesstelsel kunnen binnenhalen. Daarvan kwam het echter niet, door tegenwerking van de PvdA maar ook omdat de Tweede Kamerfractie afstand nam van een nieuw kiesstelsel. De Graaf trad in maart 2005 af als minister en werd opgevolgd door Alexander Pechtold.
Mede vanwege de aanhoudende electorale teruggang zwol in D66 de kritiek op het kabinetsbeleid aan. Nadat fractievoorzitter Dittrich begin 2006 zonder overleg met de D66-bewindslieden de voorgenomen militaire missie naar Afghanistan had afgewezen, trad hij af. De reputatie van D66 kreeg opnieuw een flinke dreun en bij de gemeenteraadsverkiezingen van 7 maart 2006 werd een groot verlies geleden. De kwestie-Hirsi-Ali leidde uiteindelijk tot de definitieve breuk tussen de Tweede Kamerfractie – onder leiding van de nieuwe voorzitter Lousewies van der Laan – en het tweede kabinet-Balkenende. In juni 2006 zei de fractie het vertrouwen op in de minister voor Vreemdelingenbeleid en Integratie, Rita Verdonk (VVD), waarna het kabinet viel.
