Группа Mayhem была основана в Осло в 1984 году гитаристом Евронимусом (настоящее имя Эйстейн Ошет), бас-гитаристом Некробутчером (Йорном Стубберуд) и ударником Кьетилем Манхеймом, которые позаимствовали название из песни Venom «Mayhem with Mercy». Сначала вокалистом был Евронимус, ненадолго на эту роль взяли Эрика Нордхейма (Messiah), а с 1985 года постоянным вокалистом стал Свен Эрик Кристиансен (Мэниак). В этом составе Mayhem записали демо Pure Fucking Armageddon и мини-альбом Deathcrush. Пластинки вышли в 1986 и 1987 годах соответственно на лейбле Евронимуса, которой назывался Posercorpse Music (позже переименован в Deathlike Silence Productions). Mayhem начинали как типичная дэт-метал-группа, основной темой которой были смерть и насилие. Но скоро в тексты добавились мотивы скандинавского язычества и сатанизма, к которому тяготел Евронимус.
В 1987 году из группы ушли Манхейм и Кристиансен. После кратковременного сотрудничества с другими вокалистом и ударником эти позиции заняли соответственно Дэд (швед Пер Ингве Олин) и Хеллхаммер (Ян Аксель Бломберг). Дэд был одержим смертью, одевался в лохмотья, наносил себе на лицо грим, делавший его похожим на труп («корпспэйнт»), и резал себе руки на концертах. В 1990 году Mayhem провели тур по Восточной Германии и сыграли в турецком Измире. Выступление в Лейпциге было записано и впоследствии издано как официальный концертный альбом Live in Leipzig. В этом же составе группа начала работать над записью первого студийного альбома De Mysteriis Dom Sathanas. Четыре написанных для него песни уже были исполнены в Лейпциге.
Дэд покончил с собой 8 апреля 1991 года, выстрелив себе в голову из ружья. Первым тело обнаружил Евронимус, который сделал несколько фотографий трупа. Одна из них позднее была помещена на обложку бутлега Dawn of the Black Hearts. Кроме этого Евронимус забрал на память кусочки черепа Дэда, которые рассылал другим музыкантам в знак уважения.
В следующие пару месяцев Евронимус в Осло открыл музыкальный магазин Helvete, который стал центром притяжения для молодых норвежских блэк-металлистов и в котором Евронимус вёл дела Deathlike Silence Productions. Тогда же Некробутчер покинул группу. Со временем на место бас-гитариста Евронимус взял Варга Викернеса, который познакомился с ним в Helvete и записи чьего проекта Burzum Евронимус издавал на своём лейбле. В Mayhem Викернес взял псевдоним Граф Гришнак. Вместе с вокалистом Аттилой Чихаром (лидером венгерской группы Tormentor, одними из пионеров блэк-метала) и сессионным гитаристом Снорре Рухом (создатель проекта Thorns) Mayhem возобновили работу над De Mysteriis Dom Sathanas. Рух не принимал участия в записи альбома, но под его влиянием Евронимус перешёл от резкой, скоростной манеры игры на гитаре к более тягучим и вязким риффам, а сочинённые самим Рухом риффы вошли в песню «From the Dark Past». De Mysteriis Dom Sathanas был записан в 1992—1993 годах в студии Grieghallen в Бергене. Свои партии Хеллхаммер записал на ударной установке, стоявшей непосредственно в концертном зале, благодаря чему качество ударных на альбоме оказалось необычайно высоким для блэк-метала. Чихар по сравнению со временем, когда он записывался с Tormentor, прошёл через множество увлечений от классического рока до монгольского горлового пения. Впоследствии, после выхода альбома, De Mysteriis Dom Sathanas не только получил известность из-за скандальных обстоятельств, сопутствовавших записи, но и был моментально распознан как важная и инновационная для блэк-метала работа.
10 августа 1993 года Варг Викернес и его друг Снорре Рух приехали из Бергена в Осло к Евронимусу, где после ссоры Викернес нанёс Евронимусу удары ножом, который он всегда носил с собой, смертельный удар пришелся в голову. О том, что могло привести к убийству, спорят до сих пор, в частности, в качестве причин называют конфликт Варга и Евронимуса по поводу доходов от продажи дисков Burzum и борьбу за лидерство в сатанинской организации The Inner Black Circle of Norway, которую возглавлял Евронимус и в которую входили Викернес и ряд других музыкантов. Сам Викернес позднее писал, что Евронимус планировал его убийство и что Викернес фактически прибегнул к самообороне, а большинство из ран на теле Евронимуса образовались от падения на осколки стекла при скатывании с лестницы, а не были нанесены Викернесом. Викернес был арестован через несколько дней и позже приговорён к 21 году тюрьмы за убийство Евронимуса и поджоги церквей, Рух, ждавший Викернеса внизу, получил 8 лет за соучастие в убийстве. Группа, единственным участником которой остался Хеллхаммер, де-факто прекратила существование. Процесс над Викернесом бурно освещался в норвежской прессе.
Альбом De Mysteriis Dom Sathanas вышел в 1994 году. Задержка была вызвана тем, что родители Евронимуса не хотели видеть на альбоме имя Варга Викернеса и настаивали на том, чтобы Hellhamer переписал партии бас-гитары. Поскольку он не умел играть на басу, на альбоме остались партии, записанные Викернесом, но в буклете из музыкантов были упомянуты только Хеллхаммер и Евронимус.
Уже на похоронах Евронимуса Хеллхаммер и Некробутчер договорились воскресить Mayhem. Вокалистом они взяли Мэниака, с которым Некробутчер продолжал поддерживать контакт. В конце 1994 года роль гитариста была предложена девятнадцатилетнему Руне Эриксену (Бласфемер), практически неизвестному даже внутри сцены. Их первой совместной записью стал мини-альбом Wolf's Lair Abyss (1997) и в том же году Mayhem начали давать концерты в новом составе. Поворотным пунктом для группы стал полноформатный альбом 2000 года Grand Declaration of War. На нём в полной мере проявилось мастерство Эриксена, «ломаная» гитара которого создавала футуристические ландшафты, а довершали дело разнообразные вокальные техники Мэниака. Grand Declaration of War разделил фанатов группы, часть из которых не мыслила группу без Евронимуса и с новым звучанием.
В 2004 году вышел третий альбом Chimera. Вскоре после этого группу покинул Мэниак. По словам Некробутчера, это произошло после стычки между вокалистом, который из-за страха сцены начал напиваться перед концертами, и разозлённым этим Эриксеном. Обязанности вокалиста принял Аттила Чихар.
Альбом 2007 года Ordo Ad Chao выделялся сложной структурой песен и одновременно намеренно низким качеством записи, однако стал самой успешной записью группы в норвежском чарте, в котором попал на 12-ю строчку, и получил национальную музыкальную награду Spellemannprisen как лучший металлический альбом года.
В 2008 году Бласфемер, основной автор музыки на трёх последних альбомах, объявил об уходе из Mayhem. Он уже несколько лет постоянно жил в Португалии и предпочёл концентрироваться на работе в Aura Noir и собственном проекте Ava Inferi. Для дальнейших концертных выступлений к группе присоединился Кристер Дрейер (Морфеус) из Limbonic Art, а с осени 2009 года — второй гитарист, известный под псевдонимом Сильмаэт.
16 ноября 2009 года музыканты Mayhem вместе с тур-командой были арестованы за разгром отеля в голландском Тилбурге. Ущерб, нанесенный гостинице, составил около 5000 евро. В сентябре 2010 года Mayhem впервые отыграли шоу в Новой Зеландии в рамках австралийского турне.
В 2011 году Сильмаэта сменил Мортен Иверсен (Телош), игравший со многими норвежскими группами, включая Gorgoroth и 1349, и в собственном проекте Nidingr. В 2012 году Некробутчер рассказал, что группа работает над новым материалом. Пятый альбом Esoteric Warfare был издан 9 июня 2014 года. Основным автором музыки был Телош, тексты о паранойе, контроле сознания и психотронном оружии написал Аттила. Рецензент Pitchfork охарактеризовал Esoteric Warfare как крепкую, сбалансированную работу, не достигающую крайностей экспериментаторства предыдущих альбомов, но представляющую собой не шаг назад, а скорее упорядочивание.
В 2016-2017 годах группа провела тур, в котором полностью играла альбом De Mysteriis Dom Sathanas. В декабре 2016 года запись концерта в Норрчёпинге была издана как Mysteriis Dom Sathanas Alive.
