Al-Nassr foi estabelecido em 1955 pelos irmãos Husein e Zeid Al-Ja'ba em sua casa na rua Al-Ataif em Riade. O treinamento ocorreu em um antigo campo de jogos em Gashlat Al-Shortah, ao oeste do Jardim Al-Fotah, onde havia um pequeno campo de futebol e uma pequena sala para armazenar bolas e camisas. Além dos irmãos Al-Ja'ba, Ali e Issa Al-Owais estiveram entre os primeiros trabalhadores no clube. Segundo maior campeão Saudita com 9 ao além de 6 Copa do Rei e 3 Copa do Príncipe, em dezembro de 1995 o clube jogou sua única final na Champions da Ásia, perdendo por 1-0 na prorrogação a final para o Seongnam em casa no Estádio Internacional Rei Fahd.
O clube funcionou como um clube amador até 1960. O clube representou a região da AFC na primeira Copa do Mundo de Clubes da FIFA no Brasil em 2000. Na competição, o Al-Nassr jogou contra o Real Madrid perdendo de (3-1) no Estádio do Morumbi,uma vitória de (4-3) no Morumbi sobre o Raja Casablanca e perdendo por (2-0) para o Corinthians, que viria a ser o campeão, terminando em 3º no grupo. Al-Nassr ganhou o prêmio Fair Play da competição e Fahad Al-Husseini foi o artilheiro do clube com 2 gols.
Nota: Se procura o clube dos Emirados Árabes Unidos, veja Al-Nasr.
Arábia Saudita
Recopa da AFC: 1 (1998)
Campeonato Saudita: 9 (1975, 1980, 1981, 1989, 1994, 1995[3] 2014 , 2015 e 2019)
Copa do Golfo: 2 (1996 e 1997)
Brad Jones 
Maicon
Kim Jin-su
Gonzalo Martínez
Abderazak Hamdallah
Smahi Triki
Emad El-Nahhas
Ahmed Musa
Moussa Saïb
Youssouf Falikou Fofana
Ohene Kennedy
Razak Omotoyossi
Nashat Akram
Hristo Stoichkov
Hussein Ozmidjani
Denílson
Gonzalo Martínez
Julio César Baldivieso
Otilino Tenorio (†)
Alberto Blanco
Don Revie
Ilie Balaci
Henri Michel
Rui Vitória
Milan Živadinović
Foeke Booy
Rodion Gačanin
Jorge da Silva
Walter Zenga
