Stynes saw the success that his older brother the late Jim (who won the All-Ireland minor football championship with Dublin in 1984) had in Australian rules football's Australian Football League, and was recruited to his brother's club, Melbourne. He debuted in 1992 but played only 2 games for no goals, and at 190 cm was touted as a possible key position player. His career did not blossom, however, and he returned to Ireland.
Brian Stynes was on Dublins winning team in the 1995 all-Ireland senior football championship against Tyrone at Croke Park. Stynes was awarded an allstar for his performances in 1995. Brian played his club football for Ballyboden St Endas.