Il est élu au Sénat de Géorgie en 1970[2]. Il y dirige la minorité républicaine de 1974 à son départ de l'assemblée en 1989[1]. Président du Parti républicain de Géorgie de 1985 à 1987[2], il participe à la campagne présidentielle de George H. W. Bush de 1988[1]. Ce dernier le nomme directeur des Corps de la paix lorsqu'il est élu président des États-Unis[1],[2]. Il est en poste entre 1989 et 1991.
Lors des élections sénatoriales américaines de 1992, Paul Coverdell est candidat face au sénateur démocrate Wyche Fowler. Pendant de nombreux mois, il fait diffuser des publicités négatives à l'encontre du sénateur sortant, qu'il accuse d'augmenter les taxes et de ne pas soutenir la guerre du Golfe[3]. Le , il est légèrement devancé par le sénateur sortant, rassemblant 48% des voix contre 49% pour Fowler. Cependant, puisque aucun candidat n'atteint 50% des suffrages, un deuxième tour est organisé. À la fin du mois de novembre, il est remporte de justesse l'élection, malgré l'important soutien du nouveau président Bill Clinton à son adversaire[3],[4]. Ce second tour est cependant marqué par une forte abstention (38% de participation contre 72% au premier tour)[3].
Il est réélu avec environ 52% des voix face au millionnaire Michael Coles lors des élections sénatoriales de 1998[5], malgré l'inquiétude de certains républicains à l'égard de son style discret[2]. C'est la première fois qu'un sénateur républicain est réélu en Géorgie depuis la Reconstruction[6].
Proche de George H. W. Bush et du chef de la majorité républicaine au Sénat Trent Lott, Coverdell s'occupe de la liaison entre le Sénat et la campagne présidentielle de George W. Bush en 2000[2],[6].
