Фирма Gull наняла известного по тем временам продюсера Роджера Бэйна, который работал с Black Sabbath на заре её карьеры и который был известен в качестве продюсера тяжёлой музыки. Участники Judas Priest полностью доверились ему и его вкусам и записали свой первый альбом, названный Rocka Rolla. Он был выпущен 6 сентября 1974 года. Однако выпуск пластинки обернулся большим разочарованием для музыкантов. Прежде всего, запись на виниле была крайне тихой, хотя в студии музыканты играли «достаточно громко и тяжело». Предполагалось, что при переносе ленты на прототип пластинки уровень громкости обрезали, чтобы он не выходил за рамки технических стандартов.

Другим разочарованием стало то, что на обложке альбома была изображена пробка от кока-колы с выведенным на ней названием альбома. По идее авторов, этот ход должен был расширить аудиторию слушателей альбома. В фирме Gull Judas Priest уверяли, что не стоит появляться на свет со штампом хэви-металической группы. По своей неопытности музыканты согласились на это. Однако неудачи выпуска альбома компенсировались тем, что за Judas Priest закрепилось звание концертной группы. Первый квартал 1975 года группа проводила выступления в Скандинавии, затем в Великобритании. В Норвегии Judas Priest опять дала концерт в том клубе, после выступления в котором удалось заключить контракт, и снова он сыграл положительную роль в истории коллектива. После концерта музыкантов пригласили на рок-фестиваль в Рединге. Выступление на этом фестивале в августе 1975 года стало поворотной точкой в развитии группы, так как на неё обратили внимание журналисты британской и мировой музыкальной прессы.

Смена барабанщиков. Первые американские гастроли (1975 — 1977)

Вскоре после выступления в Рединге Джон Хинч покинул Judas Priest. В коллектив вернулся Алан Мур, который играл в группе три последних месяца 1971 года. Осень 1975 года Judas Priest провела в репетициях нового материала. Уже в декабре группа отправилась в лондонскую студию Morgan Studios для записи второго альбома. Хотя бюджет, выделенный для записи, был скромным, опыт, приобретённый музыкантами во время записи первого альбома, Rocka Rolla, помог провести запись на более высоком уровне. В результате второй студийный альбом, названный Sad Wings of Destiny, получился удачным и оправдал ожидания группы. Он поступил в продажу 23 марта 1976 года. В апреле Judas Priest отправилась в крупные гастроли по Великобритании, которые закончились лишь в конце июня. Sad Wings of Destiny был принят лучше, чем его предшественник, и на концертах собиралось больше людей. Однако доходы группы не компенсировали многочисленных расходов. Чтобы сохранить коллектив и не потерять возможности хотя бы иногда выезжать на концерты, участникам Judas Priest снова пришлось устраиваться на дневную работу. Гленн Типтон устроился работать садовником, Йен Хилл подрабатывал водителем, а Даунингу посчастливилось найти совсем лёгкую работу, на которой, по его словам, он ничего не делал, однако получал 15 фунтов в день. Роб Хэлфорд вспоминал, что это было тяжёлое время для Judas Priest, однако их девиз был «держаться вместе», и они этому девизу не изменили.

В 1976 году в Великобритании произошла «панк-революция». Так как панк-рок становился всё популярнее, то группы, играющие хард-рок и хэви-метал, подвергались острой критике в музыкальных изданиях. Judas Priest не стала исключением. Гленн Типтон вспоминал, что это был трудный период для Judas Priest, так как «всякий длинноволосый музыкант, играющий тяжёлый рок, подвергался потоку оскорблений в печати». Однако к концу 1976 года новые менеджеры Judas Priest сумели заинтересовать крупную международную корпорацию CBS. Они разорвали контракт с фирмой Gull и подписали контракт с CBS. Теперь он распространялся на весь мир. Тут же группа приступила к репетициям, которые проходили в женском монастыре. Типтон вспоминал, что монахини, по всей видимости, разрешили им репетировать там, потому что думали, что Judas Priest является церковной группой; они даже пригласили музыкантов выступить на чаепитии в монастырском саду, однако участники Judas Priest отказались. К записи новой пластинки группа приступила в январе 1977 года, пригласив продюсером бывшего басиста Deep Purple Роджера Гловера. Барабанщик Алан Мур во второй раз покинул группу, на замену ему пришёл сессионный музыкант Саймон Филлипс ({{lang-en|Simon Phillips}}). Новый лейбл и продюсер обеспечили группе все условия для написания качественного альбома. Им стала пластинка Sin after Sin, которая вышла в продажу в апреле 1977 года. Вскоре после её выхода Саймон Филлипс, к большому огорчению остальных музыкантов, отказался дальше принимать участие в работе коллектива. На смену ему был приглашён Лесли Бинкс. После хорошо организованных гастролей по Великобритании, которые закончились в лондонском театре «New Victoria», группе предстояла поездка на гастроли в США. Гленн Типтон вспоминал, что это казалось группе «путешествием в нечто нереальное». Первый американский концерт Judas Priest состоялся 17 июня 1977 года в городе Аморилла, за ним последовало множество концертов по штату Техас и югу США, среди которых были и два выступления на «разогреве» у Led Zeppelin.