Уйдя из Metallica, в апреле 1983 года Дэйв Мастейн (Dave Mustaine, род. 13 сентября 1961 года), вместе с гитаристом Bobby Cromwell и ударником Mick Lesnick, основал в Лос Анжелесе трио Fallen Angels. Данный состав просуществовал полгода, а потом распался, после чего все тот же Мастейн, теперь уже вместе с басистом Dave Effelson и ударником Lee Rash, составили проект Megadeth. Свой первый концерт они дали 17 апреля 1984 года в одном из клубов Сан-Франциско. Какое-то время в группе проработал Керри Кинг из Slayer, правда, лишь в качестве сессионного музыканта.
Так Megadeth колесили по клубам года два, пока не заключили долгосрочный контакт с фирмой Combat, принадлежавшей корпорации Music For Nations. Тогда же появился второй гитарист - Chris Poland. И тогда же Ли Рэш вышел из команды, освободив место для Gar Samuelson.
Состав Megadeth окончательно стабилизировался к 1984 году. После чего Megadeth смогли наконец-то засесть в студию и приступить к записи своего дебютного альбома, который имел необычно длинное название: "Killing Is My Business... But Business Is Good". Так случилось, что, когда пол альбома было записано, команду покинул продюсер и музыкантам, которые были достаточно неопытны, пришлось завершать альбом своими силами. Соответственно, качество материала, а также и саунда, оставляло желать лучшего. На альбоме трэш переплелся с heavy-metal и авангардным джазом. Однако, диск принимался не так уж и плохо, и его коммерческий успех был несомненен. На альбоме появился также и символ Megadeth, который группа использовала и в дальнейшем: скелет в каске по кличке Vic. Vic олицетворял победителя в грядущей атомной войне, точнее, то, что скорее всего останется от этого победителя.
Megadeth предприняли турне по Европе, засветились на концертах с King Diamond, Exciter и Death Angel. В 1986 году истек срок контракта с Combat, и работа над новым студийным альбомом группы продолжилась на Capitol. Альбом стал прорывом к международному успеху, заняв высокие места в хит-парадах большинства стран. По следам альбома последовало мировое турне с Элисом Купером.
Но не все было ясно на небосклоне Megadeth. В группе шли постоянные трения, приведшие в марте 1987 года к увольнению ударника. Замену нашли поблизости - взяли рабочего со сцены. После этого барабанщиков меняли еще долго, и провожавшиеся разногласия привели к уходу Поланда. В итоге, в составе появился гитарист Jay Reynolds из Malice, вскоре поменявшийся на Jeff Young из Broken Silence.
Новый альбом Megadeth превзошел предыдущий, став на тот период одним из лучших в истории heavy-metal. "So Far, So Good... So What!" был записан и смикширован в промежутках между гастролями. Диск вошел в американский Топ 30 и занял 18 место в Англии. Курьезная вещь: первым серьезным хитом Megadeth стала не собственная вещь, а ковер-версия знаменитой песни Sex Pistols "Anarchy In The U.K.", позже выпущенная в виде сингла. На альбоме музыка группы стала более мирной и доступной для массового восприятия, но смогла при этом остаться экспериментальной.
Начало 1988 года прошло в гастролях с такими командами, как Warlock, Sanctuary и Dio. Последовало выступление Megadeth на фестивале "Monsters Of Rock". А затем звезда Megadeth оказалась перед вероятностью потускнения на веки вечные: у Мастейна начались проблемы с алкоголем, и вместе с басистом он был помещен в реабилитационный центр, откуда вскоре сбежал. Само собой разумеется, тем временем группа развалилась.
В 1989 году Мастейн, разобравшись со спиртными проблемами, взялся за реформацию группы. На ударные пришел Nick Menza. Megadeth записали ковер-версию сингла Alice Cooper "No More Mr.Nice Guy", вошедшую в звуковую дорожку к фильму "Electroshock". Мастейн уволил Ли Олтиса, и его место занял гитарист-виртуоз Марти Фридман (Marty Friedman, род. 8 декабря 1964 года). В таком составе был записан "Rust In Peace". Куда как более мирный альбом, на котором Megadeth потеряла немалую часть аудитории, предпочитавшей более тяжелую музыку, и приобрели премию музыкальную "Грэмми", впервые в тяжелом роке.
В 1990 году произошло историческое турне, называвшееся "Clash Of The Titans" и стартанувшее 15 сентября. В нем участвовали Megadeth, Slayer, Testament и Suicidal Tendencies. Ездили по Европе.
Megadeth активно концертировали. Следующий альбом был записан в прежнем составе. "Countdown To Extinction", появившийся в 1992 году, стал платиновым через 3 недели после появления в продаже. Новый Megadeth был значительно медленнее и мелодичнее. Однако, при этом он не стал легче, саунд оставался тяжелым. Альбом занял в Billboard второе место (!!!). После Metallica, добравшихся до первого места, этот случай является беспрецедентным. И - снова турне по всему миру. Вышедший в 1993 году альбом "Youthanasia" укрепил успех команды.
В 1995 году вышел альбом "Hidden Treasure", содержащий B-стороны синглов, музыкальные дорожки к фильмам и тому подобное. В том же году Мастейн отыграл гитарные партии на альбоме группы MD.45.
Новейший, девятый по счету альбом группы "Megadeath" вышел 6 сентября. Сначала об этом заявила группа, а позже подтвердила компания "Кэпитол". Новый диск получил название "Риск". Одна из новых песен - "Сокруши их", так же появилась на звуковой дорожке к новому фильму с участием Жан-Клода Ван Дамма "Универсальный солдат - Возвращение".