В 1994 году выходит второй альбом группы — «Protection». В музыке Massive Attack стало больше живых инструментов, меньше семплов. И без того неспешный темп стал ещё более медленным и тягучим. Вокалистами на сей раз были приглашены Трэйси Торн (Tracey Thorn) и Николетт (Nicolette). Также в записи альбома принял участие композитор Крэйг Армстронг (Craig Armstrong), он записал партии пианино в «Heat Miser» и «Weather Storm» и провел оркестровую партию в «Sly». Tricky тоже помогал группе в работе над альбомом, но позднее, как и Шара Нелсон, сосредоточился на своей сольной карьере. Именно в этот момент музыкальные критики для определения стиля бристольского саунда, представленного Massive Attack, Tricky и Portishead, запустили в оборот термин «трип-хоп».

В 1995 году вышел альбом ремиксов «No Protection». Ремиксы для него сделал известный дабовый музыкант Mad Professor. Примерно в то же время, совместно с Трэйси Торн была записана песня «The Hunter Gets Captured By The Game» для саундтрека к фильму «Бэтмен Навсегда». Во время работы над этой композицией, которую у Massive Attack никак не получалось закончить, Дель Наджа обратился за помощью к случайно находившемуся на той же студии продюсеру Нилу Дэвиджу. С ним впоследствии Massive Attack проработают более двенадцати лет, и Дэвидж окажет значительное влияние на звучание группы. В 1996 году Massive Attack основали собственный музыкальный лейбл «Melankolic», на котором выходили записи Хораса Энди (Horace Andy), Крэйга Армстронга, Льюиса Паркера (Lewis Parker), и групп Day One, Sunna, Alpha.

1998 год ознаменовался выходом самого успешного альбома группы — «Mezzanine». Подчеркивая стремление группы в каждом новом альбоме уходить от звучания предыдущего, Massive Attack плавную мягкость «Protection» сменили на новый жесткий, тяжелый, насыщенный звук. Речитативы 3Д и Дэдди Джи стали принимать параноидально-депрессивный оттенок, оркестровые и клавишные партии Армстронга сменились на звук живых гитар и агрессивных синтезаторов. Вокал Хораса Энди перестал даже отдаленно напоминать о его принадлежности к рэггей-миру. Единственным проблеском тепла и нежности на диске стало появление Элизабет Фрэйзер (Elizabeth Fraser) из группы Cocteau Twins, которая исполнила голосовые партии в нескольких песнях, в том числе и знаменитой «Teardrop», которая стала одним из главных хитов группы и вошла во множество чиллаут-сборников. Музыкальная тема из этой песни стала сопровождением для заглавных титров популярного телесериала «Доктор Хаус» (в американской версии сериала), а также она звучала в одной из серий первого сезона телесериала «Побег из тюрьмы» и в начале 16 серии 1 сезона телесериала «Зачарованные». «Teardrop» оказалась не единственной песней с «Mezzanine» покорившей мир кино. Песня «Angel» с этого альбома прозвучала в более чем десятке фильмов и сериалов (например, в фильме Гая Ричи «Большой куш»), а также является саундтреком к игре «Vampire The Masquerade Bloodlines» . Другими музыкантами на этот хит было написано множество кавер-версий, даже металлисты Sepultura не прошли мимо него. Сам же альбом вошел в 500 лучших музыкальных альбомов всех времен, по версии журнала Rolling Stone.

Однако поиск нового звучания привел к расколу внутри группы. Надоевшие друг другу музыканты ездили на запись в студию по отдельности, но даже такая мера не помогла сохранить коллектив. После окончания записи альбома группу покинул Эндрю Ваулз. Оставшиеся участники тоже на длительное время предпочли совместному творчеству сольные проекты: Роберт Дель Наджа стал больше времени уделять изобразительному искусству (помимо музыки, он ещё художник и дизайнер), а Грант Маршалл стал как и прежде давать сольные диджей-сеты в клубах. Надо заметить, что Роберт Дель Наджа ещё во времена The Wild Bunch увлекался граффити (известно, что он большой друг известного художника Банкси), а позже оформлял обложки для Massive Attack и проявлял повышенный интерес к фотографии. Во время паузы в работе группы, он смог уделить изобразительному искусству куда больше времени. В результате, ограниченным тиражом была выпущена книга «Fitting In» с его художественными работами. Также Роберт принял участие в визуальном оформлении альбомов и клипов группы UNKLE. Кроме того, Роберт Дель Наджа стал много времени уделять благотворительной деятельности и протестам против военных действий. Грант Маршалл, тем временем, периодически устраивал диджей-сеты, но в основном все свое время посвятил своей семье.