Colosimo begon in 1997 als profvoetballer bij Carlton SC in 1997. In 2000 maakte hij de overstap naar South Melbourne FC, waar de middenvelder slechts één seizoen speelde. Colosimo koos in 2001 voor een Europees avontuur, maar zowel bij Manchester City FC als Royal Antwerp FC kwam hij nauwelijks aan spelen. Colosimo keerde daarom in 2002 weer terug naar Australië om bij Perth Glory te gaan spelen. Vervolgens speelde hij voor Parramatta Power (2003-2004) en het Maleise Pahang FA (2004), waarna Colosimo in 2005 terugkeerde bij Perth Glory. Deze club verhuurde hem in 2007 in de periode tussen de A-League van 2006/2007 en 2007/2008 aan Sivasspor. Van 2008 tot 2010 speelde hij bij Sydney FC.