Stained Class, Killing Machine, Unleashed in the East (1978 — 1979)

После окончания гастролей в США группа приступила к работе над новым альбомом с продюсером Деннисом МакКеем. Новый альбом Stained Class вышел 10 февраля 1978 года. Название пластинки является игрой слов с {{lang-en|Stained glass}} (витражное стекло): {{lang-en|Stained class}} приобретает совершенно другое значение — «запятнанный, запачканный класс (общества)». В альбоме Stained Class присутствуют элементы спид-метала и трэш-метала, песню «Exciter» часто называют предшественницей спид-метала, а самих Judas Priest после этого альбома стали называть «дедами трэш-метала». Примечателен и тот факт, что на обложке альбома был представлен новый логотип группы, который с небольшими изменениями остался у неё и до сегодняшнего дня.

На последующих гастролях Роб Хэлфорд, ранее менявший по несколько сценических костюмов за одно выступление, стал появляться на сцене в чёрной одежде. К осени 1978 года вдобавок к чёрной одежде в имидже группы появились изделия из металла, в то время нехарактерные для металлистов. Именно тяга Роберта к коже и металлу вдохновила одну из песен («Hell Bent for Leather») следующего альбома Killing Machine, который вышел в свет в ноябре 1978 года.

Незадолго до выхода Killing Machine группа впервые выступила в Японии. От японских гастролей у коллектива остались хорошие впечатления. В качестве синглов были выпущены песни «Evening Star», «Rock Forever» и «Take On the World», которая заняла 14 место в чарте «Billboard Top Pop Singles». Популярность группы продолжала расти.

Judas Priest была приглашена на престижную в то время еженедельную передачу «Top of the Pops». Альбом получил статус «золотого» по сертификации RIAA 10 ноября 1989 года. Вскоре группа отправилась в одну из телестудий BBC, чтобы снять клипы для своих песен. Всего было снято две версии «Take On the World», «Killing Machine», «Rock Forever» и «Evening Star», везде Роб пел под фонограмму. На сцене Хэлфорд стал появляться с хлыстом и иногда даже с автоматом, из которого стрелял. Однако при записи клипов хлыстом пользоваться ему запретили в связи с конфликтом с дуэтом Донни и Марии Осман. Для американского рынка название альбома было изменено на Hell Bent for Leather, отличием от Killing Machine стало также включение в американскую версию альбома бонус-трека «The Green Manalishi (With the Two-Pronged Crown)». Её появление в альбоме было связано с тем, что американское отделение компании CBS настояло на том, чтобы для американского издания группа записала кавер-версию. Это было вызвано необходимостью раскрутки коллектива на радио. Было рассмотрено несколько вариантов, и в конце концов музыканты остановили выбор на песне «Green Manalishi» группы Fleetwood Mac, впоследствии ставшей чуть ли не основным хитом на альбоме.

Как и следовало ожидать, американское турне, включавшее 45 концертов, прошло с большим успехом, а билеты на три концерта в лос-анджелесском Starwood Club были распроданы полностью.

Летом 1979 года на несколько недель группа отправилась в студию Starkling Studios, принадлежащую Ринго Старру, для сведения концертных лент, накопленных во время гастролей по Японии. Первоначально эту запись японское отделение CBS — Sony Records —, обратившее внимание на огромный успех турне, намеревалось издать только для японских поклонников Judas Priest. Но после сведения плёнок музыканты остались настолько довольны результатом, что первый концертный альбом было решено выпустить во всём мире. Альбом Unleashed in the East вышел в сентябре 1979 года. Спустя много лет известный рок-журналист Джефф Бартон назовёт эту запись альбомом, который лучше всего характеризует группу образца 70-х годов. Но сразу после своего появления пластинка вызвала далеко не однозначную оценку: чересчур отшлифованный звук вызвал подозрения в том, что запись была доработана в студии, уже после того как концерт состоялся.