McMahon started playing football at a young age. In 1954, he helped St Michael's College to win the Dunloe Cup for the first time, which brought him to the attention of the Kerry minor team. He played for them in 1955, where they were beaten in the Munster Minor Football Championship final by Tipperary.[1]
While attending college in Dublin, where he played for the Clan na nGael club in Raheny for two years, working his way up from the club's junior team to the senior team. Later, while training as a solicitor with his uncle in Cashel, County Tipperary, McMahon offered to play for Tipperary, but was denied, allegedly on the grounds of being part of the McMahon family from Fethard, who seemingly were not renowned Gaelic footballers.[3]
McMahon played with the Kerry senior football team between 1959 and 1962, winning two All-Ireland medals in that time. His debut was against Cork in the 1959 Munster Senior Football Championship final, where he scored 2-2 in the first half, led match commentator Michael O'Hehir to say: "This morning, Garry McMahon was a son of a famous father, this evening Bryan McMahon is the father of a famous son".[1] He was attributed with scoring the fastest goal ever in an All-Ireland SFC final - a fisted goal after 34 seconds against Roscommon, in what was the first live televised All-Ireland final in 1962.[3] This record stood for 58 years, until 2020, when Dean Rock knocked more than 20 seconds off it.[2]