В течение первой половины 1976 года Sex Pistols выступали по клубам Лондона, с лета того года стали выезжать на гастроли в провинцию. У Sex Pistols появился постоянный концертный звукорежиссёр, Дэйв Гудман, который помог группе создать плотный громкий звук, характеризующийся в бесперебойных ударных и искаженном звуке лидер-гитары. Пение Роттсна состояло из аффектированных, пародирующих кокни возгласов, пронзительно пропсвасмых. Никаких пластинок и радиотрансляций не было, однако известность группы росла быстрыми темпами в среде британского андерграунда. В августе 1976 года Sex Pistols впервые показывают по телевидению (они исполнили одну из своих первых песен, «Anarchy In The U.K.»), чем вызвали у СМИ и широкой публики любопытство к панку. После этого только Макларсну удалось выйти на крупный лейбл EMI и заключить контракт. Стоит отметить, что сами музыканты не называли свою музыку «панком», они предпочитали термин «хаос». Термин «панк» (англ. Punk— подонок, хулиган) прижился благодаря прессе. К тому времени Sex Pistols были бесспорным олицетворением панка, воодушевив тысячи людей на создание групп по всей Великобритании, а также изменив мировоззрение уже существовавших (The Jam, The Clash, Joy Division, The Buzzcocks и др.)

Осенью 1976 года Sex Pistols впервые дали концерт за рубежом (в Париже) и затем выступили на первом панк-фестивале в клубе «100» в Лондоне. Тогда же вышел их первый сингл «Anarchy In The U.K.», занявший 38-е место. Через 5 дней, 1 декабря, состоялось печально известное интервью в телепередаче Билла Грюнди с участием группы и их друзей. После того, как ведущий попытался пофлиртовать с одной из девушек (которой оказалась ставшая знаменитой впоследствии Сьюзи Сью из Siouxsic & the Banshees), музыканты в прямом эфире покрыли ведущего нецензурной бранью— случай, не имевший прецедента до этого на британском телевидении. Шокировал телезрителей и тот факт, что друзья группы появились в повязках со свастикой. На следующий день со стороны прессы и разгневанных граждан Великобритании посыпались проклятья в адрес группы и телеканала Би-би-си. Начавшееся вскоре турне «Анархия» было частично сорвано: во многих городах власти запрещали концерты группы, а те, что проводились, осаждались толпами верующих, посылавших проклятья группе. С этого момента ореол скандальности окружал Sex Pistols до самого распада группы. В начале января 1977 года состоялись выступления в Амстердаме, после чего произошёл очередной скандал в аэропорту «Хитроу» (музыканты совершили акты вандализма в салоне самолёта и продолжили хулиганские выходки в гостинице).

Всё это, вместе с планами выхода нового провокационного сингла «God Save The Queen», оказалось последней каплей для EMI и 27 января 1977 год а контракт был расторгнут в одностороннем порядке. Компания выплатила группе неустойку. Тогда же в состав группы вошёл Сид Вишес, давний друг Роттена, заменивший Мэтлока, которого группа так никогда и не приняла в качестве «своего» (официально ему в упрёк ставилась любовь к The Beatles, хотя на самом деле сказывались их социальные различия). Несмотря на неумение играть на бас-гитаре, Сид Вишес оказался идеально подходящим для имиджа панк-рокера, однако его зависимость от тяжёлых наркотиков вносила всё более ощущаемый элемент хаоса вокруг группы.