Gogol Bordello известны своими театрализованными постановками концертов, которые являются смесью карнавала и комедии. Их музыка подверглась влиянию украинских и русских народных мотивов, карпатской (в основном украинской), цыганской музыки, в сопровождении аккордеона и скрипки (в некоторых альбомах и саксофона) и является объединением романса, панка, фолк-рока и рок-н-ролла.
Группа была основана в 1999 году украинским эмигрантом Евгением Гудзем. В состав вошли музыканты из России, Белоруссии, Израиля, а также Эфиопии, Эквадора и Китая. Всемирную известность Gogol Bordello завоевали благодаря сотрудничеству с Мадонной, а также участию в крупнейших рок-фестивалях - Coachella, Lollapalooza, Roskilde, Rock am Ring, Reading и Leeds. Одной из самых известных композиций группы стала песня "Start Wearing Purple":