É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.
Il envisage en 2019 de se présenter au poste de Premier ministre avant d'y renoncer[6].
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[6].