He started out in the Kärpät Oulu system. playing for their junior teams and turning pro in 2005-06. In 2007-08 Leinone signed with HPK Hämeenlinna and split two seasons between the SM-Liiga's HPK and various Mestis teams.
He played in the 2009-10 season for the Mestis team Hokki Kajaani. In 2010-11 He joined Kiekko-Laser Oulu. The team went bankrupt in December, 2011, and Leinonen then moved to Merano.