Lider i osnivač ovog neobičnog benda je Eugene Hütz, rođen u Kijevu, živio u Italiji, Poljskoj, Mađarskoj i Austriji, da bi na kraju došao u New York gdje je i počela uspješna priča Gogol Bordella. Hützov muzički ukus se kretao od izvođača poput The Birthday Party i Einstürzende Neubauten, da bi na svom životnom putu kroz različite kulture otkrio i ljepote ciganske muzike.
Stigavši u New York, okružio se živopisnom ekipom s kojom je počeo nastupati. Rezultat je bio zanimljiv spoj koji je podsjećao na fuziju politički nastrojene Mano Negre i otkačene zabave Leningrad Cowboysa. Nakon uspješnog prvog singla uslijedio je i album prvjenac koji je producirao oduševljeni Jim Sclavunos, član Caveovih Bad Seedsa. Album "Gypsy Punks - Underdog World Strike" iz 2005. producirao je moćni Steve Albini (koji je radio sa Nirvanom i Pageom & Plantom, između ostalih), a njihov album iz 2010. "Transcontinental Hustle", je producirao, niko drugi nego Rick Rubin, koji stoji iza produkcije izvođača poput Johnnya Casha, Rage Against The Machine, Adele i mnogih drugih muzičara.
Gogol Bordello se pridružuje programu ovogodišnjeg INmusic festivala, zajedno sa najavljenim izvođačima The Cranberries i Mando Diao, a festivalske ulaznice za INmusic 2012 su u prodaji u Tisak Media centrima po cijeni od 290 kuna.
Bend je gostovao na mnogim velikim glazbenim festivalima poput Roskildea, Bonnarooa, Reading and Leedsa, Lollapalooze, Rock am Ringa i Rock im Parka, Szigeta... Live nastupi Gogol Bordella su divlje fešte koje uključuju niz različitih instrumenata, ponekad i cirkusante ili pirotehniku, horove i trubače, a šaroliki kostimi su sastavni dio programa. Kakav će ludi show prirediti na INmusic festivalu, vidjet ćemo posljednjeg vikenda u junu.