I forlengelsen av Whitewater-etterforskningen begynte Starr å gjøre undersøkelser rundt presidentens privatliv, det munnet ut i den såkalte Lewinsky-saken. Rapporten om Bill Clintons forhold med Monica Lewinsky ble overlevert til Kongressen i 1998, og utgjorde grunnlaget for riksrettssaken mot Bill Clinton på nyåret 1999. Starr fikk fra flere hold kritikk for å ha vært urimelig nidkjær og detaljorientert i sin etterforsking av Clintons seksualliv. Han trakk seg som spesialetterforsker i oktober 1999.
