On 21 December 2007, it was announced on Greenock Morton's website that Millar had signed a pre-contract agreement with St Johnstone. He officially signed with the club on 1 May 2008. Millar helped St. Johnstone win the 2008–09 Scottish First Division and promotion to the Scottish Premier League. Millar continued to play regularly for St. Johnstone in the top flight and helped the club win the 2013–14 Scottish Cup. He signed a two-year contract with St. Johnstone in January 2015.