Sinds de verkiezingen voor de Provinciale Staten in 1995 ging het met D66 electoraal bergafwaarts, culminerend in het verlies van tien zetels bij de Tweede Kamerverkiezingen van 6 mei 1998. Zoals zo vaak werd de achteruitgang mede geweten aan een gebrekkige partijorganisatie. Vlak na de Kamerverkiezingen stelde het wetenschappelijk bureau van D66 in de notitie Investeren in D66 dat de partij ‘verbureaucratiseerde… We hebben een overschot aan vergaderaars en meepraters en te weinig mensen die in inhoudelijk en organisatorisch opzicht de handen uit de mouwen steken.’ Concrete aanbevelingen deed het bureau niet, in tegenstelling tot ‘Opschudding’, de interne vernieuwingsbeweging van voornamelijk jongeren die 27 moties op het partijcongres in november 1998 indiende – en met groot succes. Ze bereikte onder meer dat D66 zich ging tooien met de ideologische aanduiding ‘sociaal-liberaal’ en dat de regionale vertegenwoordiging in het hoofdbestuur (dat vanaf 2000 landelijk bestuur ging heten) werd afgeschaft. Met de invoering van een ledenraadpleging en partijreferendum (omdat zo ‘een groter deel van de leden betrokken wordt dan op een partijcongres’) kon de volgens Opschudding niet functionerende adviesraad ook verdwijnen, wat in 2002 ook zou gebeuren.
Ondanks de organisatorische hervormingen hield de electorale neergang aan: bij de Tweede Kamerverkiezingen van mei 2002 behaalde D66 slechts zeven zetels, wat tot grote onrust in de partij leidde. Een commissie stelde een vernieuwingsagenda op met als titel Het hoofd koel, maar met de vuist op tafel!, met voorstellen om de partijcultuur en -structuur te veranderen en de partij meer open te stellen voor niet-leden en kiezers. De Stichting Wetenschappelijk Bureau (SWB) werd omgevormd tot Kenniscentrum (en het landelijk secretariaat tot Servicecentrum). De SWB-werkgroepen maakten plaats voor ‘virtuele ateliers’, waarin leden en niet-leden elkaar via internet ‘thematisch kunnen ontmoeten’. Verder werd het lokaal partijlidmaatschap ingevoerd en de stemadviescommissie afgeschaft. In plaats daarvan kwam een systeem waarbij Kamerkandidaten participeerden in regionale voorverkiezingen waarbij niet-leden ook een stem konden uitbrengen; de daarop gebaseerde voorlopige kandidatenlijst fungeerde als stemadvies voor de leden. Het bleef bij een experiment bij de kandidaatstelling voor de Europese verkiezingen van 2004, toen slechts tweehonderd (niet-)leden aan de voorverkiezingen deelnamen. Voor de Tweede Kamerverkiezingen van 2006 werd er weer een vertrouwde stemadviescommissie ingesteld.
Het partijcongres van november 2002 besloot ook dat de partijorganisatie eenvoudiger en flexibeler moest worden. Het aantal leden van het landelijk bestuur werd teruggebracht tot zeven, waarbij het mogelijk was tijdelijk ‘projectleden’ te benoemen. Verder voerde de partij een deregulering door. Zo werd het aantal anticumulatiebepalingen verminderd en zouden de afdelingen en regio’s formeel meer ruimte krijgen.
De electorale neergang betekende ook dalende overheidssubsidies, net zoals het afnemende ledental (van 15.000 in 1995 naar minder dan 12.000 in 2000) tot verminderde contributie-inkomsten leidde. Gevolg was dat D66 moest bezuinigen op onder andere de uitgaven van het wetenschappelijk bureau en het Opleidingscentrum. Het partijblad Democraat werd verkleind en op goedkoper papier gedrukt. Verder werd er in toenemende mate gecommuniceerd via email en geïnvesteerd in een goede website. In 1995 was D66 als de derde partij van Nederland (na GroenLinks en de PvdA) met een eigen website online gegaan.
