Étudiant, il est très actif en politique. Il est président la Durca University Conservative Association (DUCA) pendant l'année universitaire 1987-1988 [2] et est l'un des six étudiants élus pour représenter Durham à la conférence annuelle NUS[3]. Il est également président du conseil d'administration de Northern Area Conservative Students (1987-1989) et membre du comité exécutif syndical national du Parti conservateur (1988-1989)[4].
Il est sélectionné comme candidat pour la circonscription parlementaire d'Altrincham and Sale West, à la suite du départ à la retraite du député conservateur vétéran Fergus Montgomery(en). La circonscription de Brady est considérée comme un siège sûr pour les conservateurs[5], puisqu'il n'y a eu que des députés conservateurs au cours de son existence. Les élections générales britanniques de 1997 se sont révélées être une bataille serrée pour le siège, mais Brady est élu avec une majorité de 1 505 voix. Il est le plus jeune député conservateur à être élu en 1997, à l'âge de 29 ans. Il est président du Comité 1922 depuis 2010.
Quand Theresa May démissionne de son poste de Première ministre le , Graham Brady annonce sa démission de la présidence du Comité 1922 avant de préparer une potentielle candidature à l'élection du nouveau chef du Parti conservateur[7]. Après avoir finalement renoncé à se présenter au scrutin remporté par Boris Johnson, il retrouve son rôle au sein du Comité 1922 en [8].
En tant que président du comité, il lui revient de définir le mode de désignation du locataire de Downing Street. Lors de l'élection d'octobre 2022 visant à désigner un successeur à Liz Truss, il a été accusé d’avoir fait en sorte d’écarter Boris Johnson[9].
Il est recommandé pour une pairie à vie en dans le cadre de la liste des personnes honorées suite à la dissolution du Parlement de 2024[11]. Le , il est créé baron Brady d'Altrincham et entre à la chambre des lords.
