Razumljivo, če upoštevamo dejstvo, da prvi mož skupine Eugene Hütz črpa svoj glasbeni navdih še iz časov tihotapljenja kaset v rodni Ukrajini. Po nesreči v Černobilu je še mladih nog moral zapustiti svoj rodni kraj in za kruhom oditi v zahodno Ukrajino.

Hütza so prevzeli ritmi in mističnost romske glasbe, ko se je selil kot begunec po predelih Poljske, Madžarske, Avstrije in Italije, preden je našel svoj prostor pod soncem v Združenih državah Amerike leta 1993. V deželi novih priložnosti je spoznal kitarista Vlada Solofara in Sasho Kazatchoffa. Pri oblikovanju njihovega novega zvoka se jim je pridružil bobnar Eliot Fergusen in prvi mož za gosli ter glavni "krivec" nenavadnih nastopov v živo Gogol Bordella Sergey Rjabtzev.

Na začetku je skupina med drugim igrala romsko glasbo na ruskih porokah, toda kmalu zatem se je njihova glasba razvila v hiperkinetično eksplozijo, ki je našla svoj prostor med newyorškimi hipsterji. Skupina je leta 1999 izdala singel When the Trickster Comes a-Pokin', ki je naznanil prvenec Voi-La Intruder. Solofarja in Kazatchkoffa so nadomestili harmonikar Yuri Lemashev, kitarist Oren Kaplan in saksofonist Ori Kaplan - ki pa kljub istemu priimku nista v sorodu.

K popularnosti skupine je precej pripomogel prav Hütz s svojimi nastopi kot nočni didžej v bolgarski restavraciji Mehanata, ko je vrtel svojo ukrajinsko-romsko-flamenko navdahnjeno glasbo. Ob nepogrešljivem metanju krožnikov ob tla.
Spomladi leta 2002 so člani Gogol Bordello odšli na turnejo po Evropi, kjer se je njihova pot šele dobro začela. Vmes je doživela tudi nekatere kadrovske spremembe, tako da jo zdaj sestavljajo ustanovni član Hütz, violinist Ryabtsev, kitarist Kaplan, harmonikar Lemashev, mojstrica tolkal in prva plesalka skupine Elizabeth Sun, basist Thomas "Tommy T" Gobena, MC in še en mojster tolkal Pedro Erazo in Oliver Charles na bobnih.

Skupina ima za seboj številne nastope tudi na največjih ameriških in evropskih festivalih, na turneje pa so se podali s skupinami, kot so Primus, Flogging Molly in Cake, svetovno pojavnost pa so dosegli tudi z nastopom z Madonno na London Live Earth koncertu leta 2007, kjer so skupaj zaigrali skladbo La Isla Bonita in v njenem filmu Filth And Wisdom.