Paatelainen began his career with FC Haka, moving on to AC Allianssi and FC KooTeePee before joining Scottish side Aberdeen in July 2004. After 10 months at Pittodrie, he returned to Finland without making any first team appearances for the Dons, joining Veikkausliiga side FF Jaro. In August 2005 he scored 5 goals in one game for Jaro, against his former club FC KooTeePee.
In January 2006, Paatelainen joined Scottish side Cowdenbeath on loan, teaming up with his brothers Mixu (then manager) and Markus. He scored 7 goals in 9 games for Cowdenbeath who would be promoted as champions of the Scottish Third Division at the end of the season. He then returned to FF Jaro in preparation for the new summer season in March 2006. In December 2006 Mikko joined TPS, a team that was then coached by his older brother Mixu. Mikko has been an outstanding goalscorer and player throughout his career also being FC TPS Turku's top scorer 2006/07. In 2010 He joined IFK Marienhamn, after three seasons with TPS . Paatelainen has been in fine goal scoring form this season scoring 8 goals.