Tuohy attracted the attention of Australian rules football recruiters from the Carlton Football Club in the Australian Football League, a club based in the northern suburbs of Melbourne. During 2009, Tuohy travelled to Melbourne to undergo a four-week trial with the club. The club was sufficiently impressed, and offered Tuohy an International Rookie contract. This contract ensured Tuohy would be recruited by Carlton; he was then selected with the club's sixth round selection in the 2010 AFL rookie draft (#73 overall) as a formality. Tuohy became the fourth Irish player to spend time on the Carlton list (and he would be only the second to play a senior game).
Tuohy began the 2010 season playing in the club's VFL-affiliate, the Northern Bullants. He developed as a tagger, and then as a rebounding half-back. He was temporarily elevated to the senior list in place of the injured Luke Mitchell in early 2011, and he made his AFL debut in Round 11 against Port Adelaide, and went on to played eleven games for the season. By 2012, he was a regular in the Carlton team, and in 2013 he played every match for the season and finished seventh in the club Best and Fairest. Over this time, Tuohy became noted for his long, accurate kicking, and regularly drifted from the backline to half-forward to kick long goals from beyond the 50m line; he had shown a similar aptitude for long-range kicking in Gaelic football, in which he was his county's designated kicker for 50m penalty kicks.