Upon graduation Conrad was snapped up by the Sydney Theatre Company to play the role of Stuey in Tony McNamara's new play "The Recruit", alongside John Howard, Leanna Walsman and Brendan Cowell, directed by Robin Nevin. He was then cast in episodes of "Always Greener" (2002) and "Water Rats" (2000) before landing the role of series regular Scott Zinenko on the medical drama "All Saints", which he played from 2001 to 2004. Coleby was nominated for the Logie Award for Best New Talent in 2002. During the final years of "All Saints", he also appeared in the Sydney Theatre Company 's production of "The Club" by David Williamson at the Sydney Opera House, and in 2005 sang the principal role of Lt Cable in Roger and Hammerstein's "South Pacific" at the Theatre Royale. Coleby portrayed student counsellor and former town resident Adam Wilde on the drama series "HeadLand" from 2005 to 2006. Coleby also appeared as a front-row footballer called Billy in the film "The Final Winter" (2006). From late 2007 until 11 June 2009, he played Roman Harris on the soap opera "Home and Away".