Группа была основана в 1980 году «Доктором» Нелле Карайличем и Сейо Сексоном под названием «Забрањено Пушење». В 1984 году выходит их первый альбом «Das ist Walter» и группа быстро становится популярна в Югославии. В 1986 году к группе в качестве бас-гитариста присоединился Эмир Кустурица. В начале девяностых группа распадается, но снова собирается в 1994 году, и 19 июня даёт концерт в Студенческом Культурном Центре Белграда. А 1997 году выходит альбом «Ja nisam odavle» посвященный жертвам войны 1992-1995 гг в Югославии. Причём новым ударником становится Стрибор Кустурица, сын Эмира. Параллельно Сейо Сексон создаёт свою группу под тем же названием. В 1998 году Нелле переименовывает группу в «The No Smoking Orchestra», и записывает саундтрек к фильму Э. Кустурицы «Чёрная кошка, белый кот» («Доктор» даже получил награду за лучшую музыку к фильму на международном биеннале киномузыки). В 2003 году в фильме Душана Милича Клубничка в супермаркете звучит песня «Lost in the supermarket» (из репертуара британской рок-группы «The Clash») в обработке «The No Smoking Orchestra» (песня вошла в сборник «Another World Is Possible»). В 2004 году последовал саундтрек к фильму «Жизнь как чудо», а в 2007 — к рок-опере «Время цыган».