Несмотря на то, что квартет записал несколько демо-пленок, в которых роль основного вокалиста взял на себя Бёрнел, было решено выдвинуть к микрофону пятого участника. В числе кандидатов на эту роль рассматривались Дэйв Вэниан (фронтмен The Damned) и Иэн Макнабб (The Icicle Works), но выбор пал на малоизвестного Пола Робертса из группы Sniff 'n' the Tears, который (как рассказывал Джет Блэк) явился на прослушивание со словами: «Я ваш новый вокалист».

Робертсу пришлось пройти проверку на прочность. «Сначала я надавил на него психически, понял, что у парня есть сила воли. Потом проверил на идейность и на вокальные данные. Наконец мы его поколотили: это было нечто вроде посвящения», — рассказывал Бёрнел в интервью еженедельнику Sounds.

Отказавшись от духовой секции, новый состав заиграл более динамичную музыку, которой соответствовала и сценическая экспрессия нового вокалиста. Далеко не все фанаты The Stranglers приняли Робертса, но Бёрнелу его манера исполнения нравилась: он сравнивал певца с Игги Попом. В отношении недовольных фэнов басист использовал проверенные методы «убеждения». «Как-то в Португалии двое зрителей принялись выкрикивать что-то оскорбительное в адрес Пола… Я снял гитару, положил её на сцену, спустился в зал и вырубил их обоих», — рассказывал Бёрнел в интервью Independent.

С начала 1990-х годов вследствие возрождения интереса к раннему творчеству The Stranglers стали выходить многочисленные переиздания. В течение десятилетия были перевыпущены — со множеством бонус-треков — все альбомы, выходившие на United Artists/Epic. В 1992 году вышла запись классического концертного выступления Live at the Hope & Anchor, в комплекте со сборником 12"-синглов. Хитом стал бокс-сет The Old Testament, куда вошли песни 1976—1982 годов. Начиная с 2001 года вышли ещё пять концертных альбомов группы и сборник трех радио-сессий на Би-би-си (1977 и 1982 годы).

В 1992 году вышел альбом Stranglers in the Night (#33 UK): критика встретила его холодно, отметив как несоответствие вокала Робертса уровню и духу («теплоте») Корнуэлла, так и отсутствие сколько-нибудь интересного песенного материала. Синглом из альбома вышел «Heaven or Hell» (#46 UK), после чего Джет Блэк временно покинул состав. Его заменил Тикаке Тобе, с которым The Stranglers записали концертный Saturday Night Sunday Morning.

В 1995 году Блэк вернулся в группу и принял участие в записи альбома About Time (#31). Рецензент журнала Encore, отметив как усилия Робертса, так и присутствие здесь сильных песен («Golden Boy and Still Life»), выразил мнение, что релиз может замедлить, но неспособен остановить скольжение группы «вниз по наклонной плоскости». Затем последовал Written in Red (#52); записанный продюсером Энди Гиллом (участником Gang of Four), он ознаменовал возвращение группы к более «синтетическому» звучанию. Презентация пластинки прошла 13 декабря 1996 года в парижском EuroDisney, но реакция на неё прессы и публики была вялой.

В 1998 году вышел Coup de Grace, где в четырёх треках из десяти вокальную партию исполнил Бёрнел. Пластинка, сюжеты которой были навеяны, с основном, поездками The Stranglers к местам давних и свежих боевых действий (Босния, Фолклендские острова), не поднялась выше #171 в британских чартах: это был наихудший показатель здесь группы за всю её историю.

Mark 3. 2000—2006 годы

В марте 2000 года Джон Эллис объявил об уходе, и его заменил гитарист Баз Уорн, игравший до этого в Small Town Heroes, группе, которая сопровождала The Stranglers в турне 1995 года. Уорн оказался в центре внимания прессы (с ним группа провела несколько европейских фестивалей) и был тепло принят фанатами Stranglers.