Due to Gold Coast United having its A-League license revoked, it was announced on 15 March 2012 that Traore had signed a two-year contract with A-League club Melbourne Victory.
Karena lisensi Gold Coast United di A-League dicabut, diumumkan pada 15 maret 2012 Traore telah menandatangani kontrak 2 tahun dengan klub A-League Melbourne Victory.