K. K. Downing, Ian Hill y John Ellis crecieron juntos en Yew Tree, West Bromwich, y se hicieron amigos durante su adolescencia compartiendo un profundo interés por la música. Influenciados por bandas como Black Sabbath, Led Zeppelin, Deep Purple y Jimi Hendrix, comenzaron a tocar instrumentos y a formar grupos. En octubre de 1970, en Birmingham, fundaron lo que sería Judas Priest, tomando el nombre de una canción de Bob Dylan, The Ballad of Frankie Lee and Judas Priest.
El nombre ya había sido usado por una banda local formada en 1969 por Al Atkins (voz), Bruno Stapenhill (bajo), John Partridge (batería) y John Perry (guitarra). Perry murió en un accidente de tráfico y fue reemplazado por Ernie Chataway. Esta primera versión de Judas Priest realizó conciertos en Inglaterra y Escocia, pero se disolvió en abril de 1970.
Atkins conoció a Downing, Hill y Ellis en una iglesia de Wednesbury. Estos músicos tenían una banda llamada Freight y buscaban un vocalista. Tras unirse, decidieron adoptar el nombre Judas Priest y comenzaron a ensayar en la casa de la suegra de Atkins. Su primer concierto como nueva formación fue el 16 de marzo de 1971 en Essington.

Bajo la dirección de Downing, la banda evolucionó desde sus raíces de blues hacia un sonido más pesado de hard rock. Tocaron frecuentemente en Birmingham y sus alrededores, abriendo para bandas como Budgie, Thin Lizzy y Trapeze. Las dificultades económicas y problemas con su mánager llevaron a la salida de Al Atkins y del baterista Alan Moore en mayo de 1973.
Fue entonces cuando Ian Hill sugirió a su cuñado, Rob Halford, como nuevo vocalista. Halford se unió junto con el baterista John Hinch, provenientes de la banda Hiroshima. Con esta formación, Judas Priest comenzó a girar por el Reino Unido y realizaron conciertos en Noruega y Alemania, consolidando su presencia en vivo.

Antes de grabar su primer álbum, la discográfica Gull Records sugirió añadir un músico adicional. Downing, reacio a incluir teclados o vientos, optó por otro guitarrista. En abril de 1974, reclutó a Glenn Tipton, exmiembro de Flying Hat Band. Tipton aportó composiciones y ayudó a reestructurar el material existente.

En agosto de 1974 lanzaron su sencillo debut Rocka Rolla, seguido un mes después por el álbum homónimo. La producción estuvo a cargo de Rodger Bain, conocido por trabajar con Black Sabbath, pero su dominio en el estudio generó desacuerdos con la banda. Bain eliminó canciones clave como Tyrant y The Ripper, y recortó otras, afectando la calidad final del disco.

El álbum fue un fracaso comercial, dejando a la banda en una difícil situación económica. Aunque intentaron negociar un salario mensual con Gull Records, la discográfica también atravesaba problemas financieros y rechazó la propuesta. Rocka Rolla fue desestimado por la banda, y la mayoría de sus canciones no se tocaron en vivo después de 1976, excepto Never Satisfied, que fue revivida en la gira Epitaph en 2011.
Para su segundo álbum, la banda asumió un mayor control creativo. Grabado entre noviembre y diciembre de 1975, Sad Wings of Destiny (1976) marcó un giro decisivo hacia un sonido más pesado y directo. Incluyó canciones que habían sido favoritas en vivo, como Tyrant y The Ripper, y presentó Victim of Changes, una épica fusión de temas de la era Atkins y de la anterior banda de Halford, Hiroshima.
Este álbum, junto con una destacada actuación en el Festival de Reading de 1975, elevó el perfil de la banda y amplió su base de fans. Sad Wings of Destiny es considerado un hito del heavy metal, influyendo profundamente en el desarrollo del género.

Tras finalizar su contrato con Gull Records, Judas Priest perdió los derechos de sus dos primeros álbumes. Su tercer disco, Sin After Sin (1977), fue su primer lanzamiento con un sello importante: CBS. Producido por Roger Glover, exbajista de Deep Purple, contó con el baterista de sesión Simon Phillips. Aunque Phillips no se quedó, Les Binks impresionó tanto que fue contratado como miembro permanente.
Con Binks, la banda grabó Stained Class (1978) y Killing Machine (lanzado como Hell Bent for Leather en EE.UU.). Binks, reconocido por su técnica y potencia, compuso partes clave de Beyond the Realms of Death, una de las canciones más emblemáticas de la banda. También participó en Unleashed in the East (1979), un álbum en vivo grabado en Japón.
Estos álbumes marcaron una evolución hacia un sonido más agresivo y técnico, alejándose de las baladas y elementos progresivos. Killing Machine introdujo un enfoque más comercial, con canciones más directas, y coincidió con la adopción de la icónica imagen de "cuero y tachuelas" que definiría su estética.

Unleashed in the East fue el primer álbum de la banda en alcanzar el estatus de Platino. Aunque hubo críticas por el uso de sobregrabaciones en un disco presentado como en vivo, demostró el poder del sonido de Priest en directo, con versiones más pesadas que sus versiones de estudio.

Les Binks dejó la banda a finales de 1979, incómodo con la dirección más comercial que quería tomar la banda. Fue reemplazado por Dave Holland, exmiembro de Trapeze. Con esta formación, Judas Priest grabó seis álbumes de estudio y uno en vivo, consolidando su éxito internacional.
En 1980 lanzaron British Steel, un disco más accesible, con canciones cortas y pegadizas como Breaking the Law, Living After Midnight y United, que se convirtieron en clásicos del rock radiofónico. Aunque más comercial, mantuvo la esencia del heavy metal.
Point of Entry (1981) siguió la misma fórmula, con canciones como Solar Angels y Heading Out to the Highway. La gira de apoyo fue extensa y bien recibida.

Screaming for Vengeance (1982) incluyó You've Got Another Thing Comin', un éxito masivo en EE.UU., además de Electric Eye y Riding on the Wind. El álbum alcanzó el doble Platino. (Take These) Chains, escrita por Bob Halligan Jr., también tuvo buena recepción.
Defenders of the Faith (1984) continuó con el éxito, aunque algunos lo consideraron una continuación de Screaming for Vengeance. En julio de 1985, la banda participó en Live Aid en Filadelfia, interpretando Living After Midnight, The Green Manalishi y You've Got Another Thing Comin'.
En 1986 lanzaron Turbo, un álbum con sintetizadores y un enfoque más comercial. A pesar de las críticas por su sonido "tecnológico", alcanzó el estatus de Platino. La gira fue exitosa y dio origen al álbum en vivo Priest...Live! (1987). Ese año, el documental Heavy Metal Parking Lot capturó a fans esperando un concierto de Priest en Maryland.
En septiembre de 1990, lanzaron Painkiller, con el nuevo baterista Scott Travis (ex Racer X). El álbum eliminó casi por completo los sintetizadores y marcó un regreso a un sonido más rápido, agresivo y técnico. Canciones como la título Painkiller y Hell Patrol mostraron una intensidad sin precedentes.

Ram It Down (1988) buscó un regreso al metal tradicional, descartando gran parte del uso de sintetizadores. Incluyó canciones reutilizadas de Turbo y nuevas composiciones. Aunque bien recibido por algunos fans, se consideró un paso atrás frente al thrash metal emergente. Dave Holland dejó la banda a finales de los 80.
La gira contó con bandas como Megadeth, Pantera, Sepultura y Testament como teloneros. El cierre fue en Rock in Rio en Brasil, ante más de 100.000 personas.
Uno de los momentos más icónicos del show era la entrada de Halford en una motocicleta Harley-Davidson, vestido con cuero y gafas de sol. En agosto de 1991, durante un concierto en Toronto, Halford sufrió un grave accidente al chocar con una plataforma de batería oculta por niebla. A pesar del dolor, completó el concierto antes de recibir atención médica. Aunque se especuló que esto influyó en su salida, Halford negó años después que tuviera relación.

En 1990, la banda enfrentó una demanda civil en EE.UU. tras el suicidio de dos jóvenes en Nevada. James Vance y Raymond Belknap intentaron suicidarse en 1985 tras escuchar Stained Class. Belknap murió; Vance sobrevivió pero falleció en 1988 por complicaciones.
Los padres alegaron que un mensaje subliminal de "do it" en la canción Better By You, Better Than Me había inducido el acto. El juicio, celebrado entre julio y agosto de 1990, concluyó con la desestimación del caso. El juez determinó que el mensaje era un resultado accidental de la mezcla de voces, no una intención deliberada.
El caso fue documentado en Dream Deceivers: The Story Behind James Vance Vs. Judas Priest (1991), y generó un intenso debate sobre la responsabilidad artística y la censura musical.

Tras la gira de Painkiller, Rob Halford dejó Judas Priest en 1991. Aunque hubo rumores de tensiones internas, Halford formó la banda Fight, explorando un estilo thrash metal más agresivo, con Scott Travis en la batería.

Permaneció vinculado a Priest por obligaciones contractuales hasta mayo de 1992. Participó en la compilación Metal Works '73–'93 y en el video homónimo, donde se anunció oficialmente su partida.
En 1998, Halford se declaró públicamente gay en una entrevista con MTV, convirtiéndose en una figura visible en la comunidad LGBTQ+ dentro del heavy metal.
En 1996, la banda reclutó a Tim "Ripper" Owens, vocalista de una banda tributo llamada British Steel. Con él, lanzaron Jugulator (1997) y Demolition (2001), además de dos álbumes en vivo: '98 Live Meltdown y Live in London.
Jugulator tuvo ventas aceptables y críticas mixtas, aunque incluyó la épica Cathedral Spires, muy apreciada por los fans. Demolition fue más experimental, con un enfoque moderno, pero no logró el mismo impacto.

Tras 11 años separados, y ante la creciente demanda de fans, Judas Priest y Rob Halford anunciaron su reunión en julio de 2003, coincidiendo con el lanzamiento del box set Metalogy. Aunque Halford había dicho antes que "nunca volvería", la reconciliación fue bien recibida.

En 2004, realizaron una gira europea y coencabezaron el Ozzfest en EE.UU., siendo considerados el acto principal por los medios. Ripper Owens dejó la banda amistosamente y se unió a Iced Earth.
En marzo de 2005, lanzaron Angel of Retribution, su primer álbum con Halford desde 1990. Fue un éxito crítico y comercial, y fue seguido por una gira mundial. Tras esta, Halford anunció la creación de su sello, Metal God Entertainment, para lanzar su material en solitario.
En 2006, remasterizó su catálogo previo y lo lanzó en iTunes, junto con dos nuevas canciones: Forgotten Generation y Drop Out.

En mayo de 2006, Judas Priest fue honrado en los VH1 Rock Honors junto a Queen, Kiss y Def Leppard. Durante la ceremonia en Las Vegas, la banda Godsmack interpretó un medley de sus clásicos antes de que Priest subiera al escenario. Halford entró en una Harley y tocaron Breaking the Law, The Green Manalishi y You've Got Another Thing Comin'.

En 2006, Halford anunció un álbum conceptual sobre el profeta Nostradamus. Describió al personaje como un "alquimista y vidente" con una vida llena de contrastes, ideal para una narrativa épica. El álbum incluiría elementos sinfónicos, coros masivos y un uso más destacado de teclados.

Nostradamus fue lanzado en junio de 2008 y fue acompañado por una extensa gira mundial. En 2009, la banda criticó la reventa de entradas y realizó conciertos en Reino Unido, Europa y América.
Entre junio y agosto de 2009, celebraron el 30º aniversario de British Steel tocando el álbum completo en cada concierto. La gira iba a ser compartida con Whitesnake, pero David Coverdale enfermó y tuvieron que retirarse.
El 14 de julio de 2009 lanzaron A Touch of Evil: Live, un álbum en vivo con grabaciones inéditas. Su versión de Dissident Aggressor ganó el Grammy 2010 a Mejor Interpretación de Metal.
En 2010, Halford reveló que se les había ofrecido una estrella en el Paseo de la Fama de Hollywood, pero no habían podido asistir. También mencionó que se consideraba una nueva gira de Nostradamus.

En diciembre de 2010, Judas Priest anunció la gira mundial Epitaph como su última gran gira. Sin embargo, en enero de 2011 aclararon que no era el fin de la banda, sino el final de las giras masivas, y que estaban trabajando en nuevo material.

El 20 de abril de 2011, K.K. Downing anunció su retiro, citando diferencias personales y creativas con la banda. Fue reemplazado por Richie Faulkner, guitarrista de Lauren Harris. Esto dejó a Ian Hill como único miembro fundador activo.
El 25 de mayo de 2011, la banda actuó por primera vez sin Downing en la final de American Idol, junto a James Durbin, interpretando un medley de Living After Midnight y Breaking the Law.
En junio de 2011, anunciaron el box set Single Cuts, una colección de sencillos.
En 2011, Halford reveló que ya tenían 12-14 canciones en desarrollo para un nuevo álbum. Aunque se esperaba para 2012, el lanzamiento se retrasó.
En septiembre de 2013, anunciaron The Chosen Few, una recopilación de canciones seleccionadas por otros músicos de metal. En diciembre, confirmaron que un nuevo álbum saldría en 2014.
El 5 de enero de 2014, aparecieron en Los Simpson, tocando Breaking the Law. Los productores los clasificaron erróneamente como "death metal", lo que generó una disculpa simbólica en la serie.
El 17 de marzo de 2014, Halford anunció en los Premios Ronnie James Dio que el álbum estaba terminado. El 28 de abril lanzaron Redeemer of Souls, el sencillo principal del nuevo disco, que lleva el mismo nombre.

El álbum fue lanzado con éxito, y se confirmó una gira de 20 fechas por EE.UU. en 2014.
En 2016, la banda comenzó a trabajar en su decimoctavo álbum. En marzo de 2017 iniciaron las grabaciones con los productores Tom Allom y Andy Sneap.

Firepower fue lanzado el 9 de marzo de 2018, recibiendo excelentes críticas. La gira comenzó en América del Norte con Saxon y Black Star Riders.
El 12 de febrero de 2018, Glenn Tipton reveló que padecía la enfermedad de Parkinson y que no podría continuar girando. Aunque se retiró de las giras, afirmó que seguía siendo miembro activo. Andy Sneap lo reemplazó en vivo.
Sin embargo, Tipton regresó al escenario en varios conciertos para tocar clásicos como Metal Gods y Living After Midnight, especialmente en los bises. Su participación continuó durante toda la gira.
En enero de 2019, la gira europea con Ozzy Osbourne fue cancelada por una infección respiratoria de este, y se reprogramó para 2020.

En 2019, Halford anunció que ya se estaba trabajando en un nuevo álbum, con Tipton contribuyendo con riffs. A pesar de su enfermedad, su participación fue clave.

Las sesiones de composición comenzaron en febrero de 2020, pero se vieron interrumpidas por la pandemia. La gira 50 Heavy Metal Years fue pospuesta de 2020 a 2021, luego a 2022 y 2023.
La banda regresó al escenario en agosto de 2021 en el festival Bloodstock, con Tipton en los bises. La gira estadounidense fue pospuesta porque Faulkner sufrió una emergencia cardíaca, y se reprogramó para 2022.
En abril de 2021 murió el exbaterista John Hinch a los 73 años. La banda continuó trabajando en el nuevo álbum, con material fuerte y prometedor.
En 2022, se anunció brevemente la salida de Andy Sneap, pero fue retractado. El nuevo disco se describió como más progresivo que Firepower, aunque fiel al sonido clásico de Priest.
El 5 de noviembre de 2022, Judas Priest fue incluido en el Salón de la Fama del Rock and Roll por Alice Cooper. K.K. Downing, Les Binks y Dave Holland fueron honrados como exmiembros. La banda tocó con Downing y Binks en el escenario, en una de las últimas apariciones públicas de Binks antes de su fallecimiento en 2025.
En octubre de 2023, antes de su actuación en el festival Power Trip, anunciaron su nuevo álbum Invincible Shield, lanzado el 8 de marzo de 2024. Los sencillos Panic Attack, Trial by Fire, Crown of Horns y The Serpent and the King precedieron su lanzamiento, mostrando un sonido poderoso y actualizado.