Al-Nassr was established in 1955 by the brothers Husein and Zeid Al-Ja'ba in their house on Al-Ataif Street in Riyadh. Training took place in an old playground at Gashlat Al-Shortah west of Al-Fotah Garden where there was a small football field and a small room to store balls and shirts. In addition to Al-Ja'ba Brothers, Ali and Issa Al-Owais were among the first workers at the club.
The club operated as an amateur club until 1960 when it was registered officially with the General Presidency of Youth Welfare. It was at this time that Prince Abdulrahman Bin Saud became head of Al-Nassr. Al-Nassr started in the second division of the league. They were promoted to the first division in 1963. During the 1970s and 1980s, the club won eightSaudi League titles, four Saudi Primer League titles, six King's Cups, two Crown Prince Cups and one Federation Cup. The team's success was built around the "Saudi Golden Trio" of Majed Abdullah, Fahd Al-Herafy and Mohaisn Al-Jam'aan.
Majed Ahmed Abdullah is Al-Nasr's all-time leader in goals scored and appearances.
In 2006–07, the club only avoided relegation on the last day of the season. After a major overhaul of playing staff Al-Nassr went on to win the Federation Cup 2008 against city rivals, Al-Hilal. The club finished third in 2009–10 securing Asian Champions League football for the following season.
Al-Nassr is the Arabic word for "victory". Clubs with the same name are found in Oman, Kuwait, Bahrain, UAE and Libya but the Saudi Arabian club was the first to take the name.
The Club's logo represents the map of Saudi Arabia with yellow and blue colors. Yellow for the gorgeous sand in the Arabian deserts, and blue for the magnificent water in the Arabian seas. Recently the old logo has been replaced by a "more modern version", but still is heavily influenced by the old club logo. The new Logo only represent the Football team while the old logo represent the Club as a whole.
Sponsorship
Al-Nassr since the start of the 2013/2014 season, has lacked any sponsors. Yet, still managed to pull through with a double, by winning the crown prince's cup, as well as finishing first in the SPL.