Cleary first entered politics when he became the New Democratic Party (NDP) candidate in the riding of St. John's South—Mount Pearl in the October 2008 federal election. His candidacy led to some controversy for him and NDP leader Jack Layton for comments Cleary had written only a couple of years before when he was a journalist. Cleary had referred to NDP supporters as a "small pocket of aging granolas and artsy-fartsies" and that they were "a mainstream party that wouldn't win an election if Jackie Layton was given a 100-seat head start." Despite his late entrance into the campaign and his previous comments he still managed to place a strong second in the riding.