Пісню було записано для дев'ятого студійного альбому Metallica Death Magnetic, що вийшов 2008 року. Одним зі співавторів, окрім звичного дуету Гетфілд—Ульріх, став новий бас-гітарист Роберт Трухільйо, для якого це були перші студійні сесії з гуртом. Під час репетицій Трухільйо зіграв риф на акустичній гітарі в стилі «фламенко», який сподобався решті музикантів — через це пісня навіть мала робочу назву «Flamingo». Пізніше до неї додалися звичні для Metallica гітарні риффи та соло, через що вона стала однією з найважчих на альбомі. Текст пісні був створений під впливом оповідання «Гончі пси Тіндала»; за словами Джеймса Гетфілда, в ній співається «про цих вовків, які полюють на вас у кошмарах». Коли прийшов час обирати список пісень для альбому, менеджер Кліф Бернштейн хотів назвати її «Hunt You Down Without Mercy» (укр.Переслідувати тебе без пощади). В результаті гурт зупинився на запропонованій Ларсом Ульрихом назві «All Nightmare Long» — грі слів від «All Night Long» (укр.Всю ніч) та «Nightmare» (укр.Нічний кошмар)[3].
«All Nightmare Long» стала найдовшою піснею з альбому Death Magnetic та вийшла окремим синглом. На неї було знято відеокліп (режисер — Роберт Шобер, також відомий як Roboshobo) в жанрі мок'юментарі. Події сатиричного псевдодокументального фільму відбуваються в СРСР, де на місці падіння Тунгуського метеорита знаходять спори, які перетворюють людей на зомбі[4].
