After retiring as a player in 2005, Paatelainen became manager of Scottish club Cowdenbeath, where he helped the club win the championship of Scottish Football League Third Division and earn a promotion. After a season coaching in his native Finland with TPS, Paatelainen returned to Scotland as manager of Hibernian. He left that position by mutual consent after 18 months. After a year out of the game, Paatelainen was appointed manager of Kilmarnock. He was Kilmarnock manager for less than one season, but enjoyed personal success during that time. He was appointed manager of the Finland national team in March 2011, a position he held until June 2015. He was appointed as Dundee United manager in October 2015, parting company with the club in May 2016 after their relegation to the Scottish Championship. He has subsequently managed Ubon United in Thailand, and the national teams of Latvia and Hong Kong.