On September 17, 2009, the New Democrats nominated Cleary as their candidate in St. John's South-Mount Pearl for the next federal election. In October 2010, Cleary announced that he would withdraw his candidacy. He stated that being a political candidate had created a conflict with his journalism work and that he wished to continue with his journalism career. He also noted that he had severed all ties with the NDP. However, in March 2011 with the announcement of a federal election, Cleary said he would return to run for the NDP again. On May 2, Cleary defeated Liberal Siobhán Coady receiving 18,332 votes to Coady's 10,670.