Gegründet wurde der Verein 1955 von den beiden Brüdern Husein und Zeid al-Ja'ba und bis 1960 operierte man als nicht offizieller Amateurverein. Heute ist der Verein einer der größten und beachtetsten des Landes. Die letzte Meisterschaft datiert aus dem Jahr 2019. Mit dem Gewinn des Asian Cup Winners Cup 1998 gelang der größte internationale Erfolg. Die Saison 2008/09 beendete der Verein auf Platz fünf und verpasste in dieser Spielzeit nur knapp die Qualifikation zur AFC Champions League 2009/10.
Im Januar 2023 verpflichtete der Verein den fünfmaligen WeltfußballerCristiano Ronaldo.[1] Der Transfer wurde von Analysten dem Vorantreiben des saudi-arabischen Marketingprojekts Vision 2030, sowie dem Begriff des Sportwashings zugeschrieben. Mit groß angelegten Bau- und Finanzierungsprojekten ist Saudi-Arabien bemüht, sein von Menschenrechtsverletzungen und Diktatur geprägtes Image zum Positiven zu verändern.[2][3] Im Juni 2023 übernahm der saudische StaatsfondsPublic Investment Fund (PIF) 75 % der Anteile an dem Verein. Der Fonds ist auch Mitbesitzer von Newcastle United und mehrerer weiterer saudischer Fußballklubs.[4] Im August 2023 verpflichtete al-Nassr Sadio Mané vom FC Bayern München.