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.