У травні 1983 року гурт вирушив до Рочестера, штат Нью-Йорк, щоб записати дебютний альбом під керівництвом продюсера Пола Керкіо. Щоправда, постійні проблеми з гітаристами згукнулися і тут: Дейва Мастейна звільнили — за наркотики, алкоголь та агресивну поведінку. Того ж дня на заміну Дейву з гурту Exodus прийшов Кірк Геммет. Мастейн не приховував своїх образ і обурення — та звинувачував нового гітариста в тому, що той вкрав його роботу та став популярним завдяки його, Мастейна, партіям. Зрештою, альбом записали, Kill 'Em All очікуваного фінансового успіху не приніс, та подарував гурту справжніх відданих фанів. Згодом журнал Rolling Stone поставив його на 35 місце в списку СТА найкращих альбомів вісімдесятих років. А вже друга платівка показала більш відчутний результат — вона опинилася посередині двохсотки Білборд.
