Paul Cellucci machte 1970 seinen Abschluss an der School of Management des Boston College; drei Jahre später bestand er an der dortigen Law School sein juristisches Examen. Er diente von 1970 bis 1978 in der Army-Reserve, aus der er im Rang eines Captain ausschied. Er war sowohl als Autohändler im familieneigenen Geschäft als auch als Rechtsanwalt in einer Kanzlei in Hudson tätig.
Von 1971 bis 1977 gehörte Cellucci dem Stadtrat von Hudson an. Im Anschluss saß er vier Legislaturperioden im Repräsentantenhaus von Massachusetts, aus dem er 1985 in den Staatssenat wechselte. Während seiner dritten Amtsperiode fungierte er als stellvertretender republikanischer Fraktionschef. 1990 wurde er zum Vizegouverneur von Massachusetts und damit zum Stellvertreter von Gouverneur Bill Weld gewählt. Als dieser zurücktrat, da er als neuer US-Botschafter in Mexiko nominiert worden war, folgte Cellucci ihm zunächst kommissarisch; 1998 gewann er dann mit 50,8 Prozent der Stimmen die Wahl zu einer eigenen Amtszeit gegen den DemokratenScott Harshbarger.
Als Gouverneur profilierte sich Paul Cellucci mit klassischen republikanischen Positionen in der Finanzpolitik. Er plädierte für eine Verschlankung des Regierungsapparats und verkündete am ersten Tag seiner Amtszeit eine deutliche Senkung der Einkommensteuer. Weitere Schwerpunkte seiner Regierungsarbeit waren eine Bildungsreform und der Kampf gegen häusliche Gewalt. Wie sein Vorgänger beendete er seine Amtsperiode nicht, da er den Posten eines US-Botschafters angeboten bekam. Im Gegensatz zu Bill Weld, dessen Ernennung niemals vom Senat bestätigt wurde, trat er dieses Amt auch an und vertrat die amerikanischen Interessen in Kanada als Nachfolger von Gordon Giffin vom 17. April 2001 bis zum 17. März 2005.
Cellucci trat vom Botschafterposten zurück, um ein Angebot des Autoteileherstellers Magna International anzunehmen. Dort war er ein Jahr lang tätig, ehe er zur Bostoner Anwaltskanzlei McCarter & English wechselte. Im Jahr 2011 erkrankte Celluci an amyotropher Lateralsklerose, an deren Folgen er im Juni 2013 in seiner Geburtsstadt Hudson im Alter von 65 Jahren starb.[1][2] Er hinterließ seine Frau und zwei gemeinsame Töchter.
