Di lontane origineorigini italiane, Coloccini iniziò la sua carriera nell'[[Argentinos Juniors]], ma esordì nel calcio professionistico con il [[Club Atlético Boca Juniors|Boca Juniors]] ([[1998]]). L'anno seguente, dopo aver vinto il torneo Apertura, passò in [[Italia]] al {{Calcio Milan|N}}, che lo acquistò per la cifra di 15 miliardi di [[Lira italiana|lire]]<ref>{{cita news|autore=G. Nigro|url=https://www.gazzetta.it/Calcio/Serie-A/storie/06-07-2019/dal-flop-amoroso-improbabili-coloccini-fabio-junior-mijatovic-mayele-peggiori-acquisti-mercato-1999-2000-340641540036/fabricio-coloccini-milan.shtml|titolo=Dal flop Amoroso agli improbabili Coloccini e Fabio Junior: i peggiori acquisti del mercato 1999-2000|pubblicazione=[[La Gazzetta dello Sport]]|data=15 luglio 2019|accesso=15 luglio 2019}}</ref>: coi rossoneri non collezionò nessuna presenza, e nel [[2000]] fu ceduto in prestito al [[Club Atlético San Lorenzo de Almagro|San Lorenzo]] dove vinse il torneo Clausura nel [[2001]]. In seguito giocò, ancora in prestito, nel [[Primera División (Spagna)|Campionato spagnolo]] con [[Deportivo Alavés|Alavés]], [[Club Atlético de Madrid|Atlético Madrid]] e [[Villarreal Club de Fútbol|Villarreal]] (conquistando la [[Coppa Intertoto 2003]]). Nel [[2004]] ritornò al Milan, militandovi solo per mezza stagione (una presenza in [[Serie A]], tre in [[Coppa Italia]] ed una in [[UEFA Champions League|Champions League]]).
Il 31 gennaio [[2005]] passa agli spagnoli del [[Real Club Deportivo de La Coruña|Deportivo la Coruña]], con cui colleziona 112 presenze e cinque gol in tre anni.
