Door het terugtreden van Jan-Willem Bertens moest D66 voor de Europese verkiezingen van 10 juni 1999 een nieuwe lijsttrekker aanwijzen. Bob van den Bos waagde net als in 1989 een kans. Hij kwam bij de stemming onder de leden over de kandidatenlijst opnieuw als eerste uit de bus, maar het partijcongres – dat reglementair de lijsttrekker koos – wees in februari 1999 Lousewies van der Laan aan. Zij was één van de aanvoerders van Opschudding, de interne vernieuwingsbeweging.
Nu D66 tot de ELDR was toegetreden, onderschreef zij het ELDR-programma, The liberal challenge for Europe geheten. Op het ELDR-congres dat het programma vaststelde, werden alle door D66 ingediende amendementen aangenomen, waaronder het voorstel bij de Europese verkiezingen te streven naar transnationale kandidatenlijsten. Naast het ELDR-programma stelde D66 een apart ‘manifest’ op met eigen inhoudelijke accenten, getiteld Het succes van Europa. Hiermee wilde de partij zich onderscheiden van de VVD, de andere Nederlandse ELDR-lidpartij en haar binnenlandse rivaal. De verkiezingsuitslag was teleurstellend, maar niet onverwacht: D66 verloor twee van de vier zetels (van de 31 Nederlandse zetels in het Europees Parlement).
De sinds de jaren negentig in Nederland toegenomen euroscepsis kreeg op D66 geen vat: zij bleef uitgesproken pro-Europa. Boe roepen is makkelijk heette het programma voor de Europese verkiezingen van 10 juni 2004. Hierin noemde D66 zich ‘een groot voorstander van de Europese gedachte’ en bepleitte zij toetreding van Turkije tot de Europese Unie – een zeer omstreden kwestie in de Nederlandse politiek. Het programma van de ELDR was in september 2003 in Amsterdam vastgesteld op een congres dat D66 en VVD samen hadden georganiseerd. Hoewel de VVD zich veel kritischer tegenover Europa was gaan opstellen gingen beide partijen voor het eerst een lijstverbinding aan. Wel voerden zij hun eigen campagne.
In 2003 was Van der Laan naar de Tweede Kamer overgestapt. Van den Bos was haar als delegatieleider opgevolgd en stelde zich (voor de derde keer) kandidaat voor het lijsttrekkerschap. Hij redde het wederom niet; nu werd hij verrassend genoeg afgetroefd door Sophie in ’t Veld. Zij was kritisch over de VVD, die in Den Haag ‘een bijna anti-Europees geluid’ zou laten horen. In de peilingen dreigde D66 uit het Europees Parlement te verdwijnen (ook omdat de kiesdrempel hoger was geworden na de uitbreiding van de Europese Unie in 2004 met tien landen), maar de partij haalde toch één van de 27 Nederlandse zetels.
In oktober 2004 werd het ‘Verdrag tot vaststelling van een Grondwet voor Europa’ in Rome ondertekend. Hans van Mierlo was namens de Nederlandse regering enige tijd bij de voorbereidingen betrokken geweest. Mede op initiatief van D66 werd hierover op 1 juni 2005 een raadplegend referendum gehouden. D66 was een uitgesproken voorstander van het verdrag, maar zag tot haar grote teleurstelling dat een ruime meerderheid tegen stemde. De partij liet zich niet uit het veld slaan. In een pamflet getiteld De Verenigde Staten van Europa kozen partijleider Boris Dittrich, In’t Veld en Van der Laan ‘voor een federale structuur waarbij de Commissie een Europese regering vormt, die gecontroleerd wordt door het Europees Parlement, dat van Europese lijsten gekozen wordt’.
