Avant de faire de la politique, Fitzgibbon est successivement électricien automobile, officier électoral, enseignant technique à mi-temps et responsable d'une petite entreprise. Il est membre du conseil de la ville de Cessnock de 1987 à 1995.
Il est élu du cabinet fantôme en tant que ministre des mines, de l'énergie et des forêts en 2003-05. En , il est nommé trésorier assistant et ministre des revenus, des petites entreprises et de la compétition dans ce cabinet.
Début 2006, quand Kevin Rudd devient chef de l'opposition, Fitzgibbon est nommé ministre de la défense de son cabinet fantôme.
Il est réélu à l'élection de 2007 et nommé ministre de la défense dans le cabinet de Kevin Rudd le [1]. Le , il doit présenter sa démission après des révélations indiquant qu'il a organisé une réunion entre un général chargé des services de santé de l'armée et son frère, à la tête d'une compagnie d'assurance. Il doit également présenter des excuses pour avoir accepté et passé sous silence des voyages tous frais payés et des cadeaux d'une riche australienne d'origine chinoise lorsqu'il était député[2].
Il est remplacé par le sénateur John Faulkner comme nouveau ministre de la Défense.
Il revient au gouvernement en étant nommé ministre d'Agriculture en , après que Kevin Rudd soit redevenu Premier ministre[3]. Il quitte ses fonctions ministérielles après la défaite des travaillistes aux élections fédérales du .
Après la défaite des travaillistes aux élections fédérales de , il déclare envisager de briguer la direction du parti, après que Bill Shorten ait annoncé sa démission[4]. Il renonce toutefois à se présenter et apporte son soutien à la candidature d'Anthony Albanese[5]. Après sa victoire, ce dernier nomme Fitzgibbon au poste de ministre de l'Agriculture et des Ressources naturelles dans son cabinet fantôme[6].
En , il annonce sa démission du gouvernement fantôme, après s'être opposé à un renforcement de la politique environnementale défendue par le parti, estimant qu'un programme plus ambitieux risquait de déconnecter les travaillistes de leur base électorale. Il exprime alors des regrets de ne pas avoir présenté sa candidature à la direction lors de l'élection de 2019, mais ne demande pas la démission d'Anthony Albanese[7],[8].
En , il annonce qu'il ne briguera pas de nouveau mandat lors des prochaines élections fédérales[9].
