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 8 ao lado do Al-Ittihad alem de 6 Copa do Rei e 3 Copa do Príncipe, em dezembro de 1995 o clube jogou sua unica final na Champions da Asia,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 vitoria 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,Fahad Al-Husseini foi o artilheiro do clube com 2 gols.
Nota: Se procura o clube dos Emirados Árabes Unidos, veja Al-Nasr.
bin Abdurahman Al-Saud
Rui Vitória
Etihad Airways
Victory's
Recopa da AFC: 1 (1998)
Copa do Rei : 7 (1974,1976, 1981,1986,1987 e 1989[3])
Don Revie
Mario Zagallo
Ilie Balaci
Henri Michel
Rui Vitória
Milan Živadinović
Foeke Booy
Edgardo Bauza
Rodion Gačanin
Jorge da Silva
Walter Zenga
