Coly moved to France when he was 7 years old.He played in all of Senegal's matches in the 2002 FIFA World Cup. After impressing at the tournament, he moved from RC Lens to Birmingham City on loan. But this proved to be a poor career move as he only managed a single Premiership appearance, against Arsenal. Coly then moved on to Perugia. In his first season with the Italian club (2003–04), he made 11 appearances but never really impressed. He spent 2004-05 in Serie C (the team descended via playoffs to Serie B then suffered "another relegation", this time in the courts), making 29 appearances and scoring twice. In the summer of 2005 he made a move to Serie A side Parma, where he has been a regular.