Cleland est candidat au Sénat des États-Unis aux élections de novembre 1996. Il remporte de justesse l'élection face au millionnaire républicain Guy Millner, qui dépense deux fois plus d'argent que lui[2]. Durant son mandat, il vote les baisses d'impôts de George W. Bush et pour la guerre d'Irak, qu'il qualifie par la suite de sa plus grosse erreur au Sénat[2].
Candidat à sa réélection en 2002, il est considéré comme en danger ayant voté à 80 % avec ses collègues démocrates dans un État de plus en plus favorable aux républicains[2]. La campagne est jugée brutale, notamment après la diffusion d'une publicité où les républicains critiquent le manque de patriotisme de Cleland (qui a perdu trois membres à la guerre) tout en diffusant des images d'Oussama ben Laden et Saddam Hussein[2],[3]. Il est battu par Saxby Chambliss (53 % des voix contre 46 %)[2].
Après le Sénat
Après sa défaite, l'ancien sénateur connaît des mois difficiles où son stress post-traumatique refait surface[3].
