Johnstone was the first selection in the 1997 AFL Draft and made his debut in the 1998 season. Johnstone took time to develop into a star player for Melbourne, and for some time was criticised in the football media for underachieving as a number 1 draft selection. In 2002 he finished equal fourth in Brownlow Medal voting, and in 2005 he won his first Melbourne Best and Fairest Award, the Keith 'Bluey' Truscott Medal, and he led the AFL in total kicks. Johnstone gradually developed into a midfielder possessing terrific vision and skill, who in 2006 for the second year in a row, led the team in the Brownlow Medal, with 11 votes. During the year he accumulated 469 disposals at 21 an outing, which included first for inside 50s and third for rebounds from 50, and was also 5th in tackles. In 2007 Johnstone struggled to capture his best form and was not helped by an Achilles tendon injury holding him to only 15 games. Johnstone produced a career-high 42 disposals in what would be his final game for the Demons in round 22 against Carlton. Throughout his career at Melbourne, Travis Johnstone was recognised as one of the AFL's most dangerous and talented midfielders; however, he often struggled for consistency, and finished in the Truscott Medaltop ten only twice.
Trade to the Brisbane Lions
On 11 October 2007 it was confirmed that the Brisbane Lions had acquired the 27-year-old midfielder from Melbourne for draft pick number 14 in the 2007 national draft, which the Lions had received from Collingwood in a trade for young ruckman Cameron Wood. This came after weeks of speculation over Johnstone's future with the club. New coach Dean Bailey was openly looking for high draft picks and Johnstone was considered a more expendable, yet of decent value. After the clubs confirmed Johnstone was now a Lion, the Melbourne Football Club was bombarded with phone calls from angry supporters who were furious that Johnstone was traded, proving that Johnstone was a very popular player among fans. In his debut for the Lions in Round 1, he amassed 20 disposals off the bench in their loss to the West Coast Eagles. The week after, Johnstone managed 22 disposals in Brisbane's nailbiting 2-point win against the Collingwood Magpies. Arguably his finest game for Brisbane to date came in the Lions' Round 8, 2008 win over Carlton where Johnstone amassed 32 disposals, six tackles and three goals. In round 11 2010, Johnstone managed a remarkable 37 disposals in a one-point loss to North Melbourne. On 28 October 2010, Johnstone was delisted from the Lions. Johnstone nominated for the 2010 AFL Draft, but began planning to play for the Palmerston Magpies.
