McKenzie grew up in the rural Victorian town of Terang. As a youth he supported the West Coast Eagles. McKenzie played for TAC Cup team, the Geelong Falcons, a team well known for producing many AFL players. He had an injury interrupted two seasons for the Falcons, due to corrective hip surgery, not playing at all in 2007 and playing only 10 games in 2008.
After playing well for the Demons' VFL affiliate side, the Casey Scorpions, for the first half of the 2009 season, McKenzie was rewarded by being promoted to the club's senior list on 23 July 2009. McKenzie made his debut for Melbourne in Round 17, 2009 against the Sydney Swans in Canberra at Manuka Oval. He played two more games for the Dees in 2009, in Rounds 21 and 22, with his best game coming against Carlton, when he amassed 16 disposals and laid eight tackles.
During the offseason McKenzie was the subject of interest from Adelaide. Adelaide coach, Neil Craig, offered him a spot on the Crows' senior list, whereas Melbourne could only offer McKenzie a spot on their rookie list, with the chance that he might be promoted to the senior list during the year. McKenzie, however, chose to repay the Demons for the faith they had put in him, by recruiting him originally, and he stayed with Melbourne, despite the possibility of reduced opportunities.
The fear that Mckenzie would have a lack of opportunities was soon relieved as he was promoted to the senior list prior to the beginning of the 2010 season, due to Max Gawn's long term injury. McKenzie has become a mainstay of the Melbourne midfield during the season and, along with other young players, such as Jack Watts, Jordan Gysberts and Jack Trengove, is considered to be the future of the club. He has also been noted for his stoppage work, particularly his clearances and tackling ability.
Despite not receiving a Rising Star nomination throughout the year, McKenzie finished the 2010 season by winning Melbourne's Coach's Award. As a reward for his performance during the season, McKenzie was elevated to Melbourne's senior list with the 81st selection in the 2010 AFL Draft.