كانت بداية النصر السعودي في 7/3/1375هـ في بداية حركة رياضية كبيرة آنذاك حيث كان النصر هو الاسم الذي اختاره مجموعة من الطلاب ليكون هو اسم ناديهم الجديد ومنزل أحدهم هو مقر النادي حيث ترأسهم في ذلك الوقت زيد الجبعاء وشقيقه حسين بالإضافة المجموعة وهم كلا من عل ي العويس وعيسى العويس وناصر بن نفيسه وعبد الرحمن الحوبان كان ذلك في شارع العطايف بمدينة الرياض.
اراد أولئك الطلاب أن يكون لفريقهم الوان مميزة وشعارا مميز يميزهم عن غيرهم من الفرق التي ظهرت في تلك الفترة والتي لم يكتب لها البقاء فأختفي سريعا كما ظهرت وكأن القـدر يقول أن النصـر وجـد ليبقى . كانت الألوان الأزرق والأصفــر هي ألـوان الفـريق وحـرف (في) -الحرف الأول من كلمة فيكتوري - باللغة الإنجليزية هو شعار الفريق وليكون أول كابتن للفريق هو اللاعب عبدالله النزهان ليليه في تلك المهمة في ما بعد اللاعب سعود العفتان الشهير بـ أبو حيدر
بدأ صراع النصر من اجل البروز على خارطة الأندية الرياضية من مصاف الدرجة الثانية حيث حقق في عام 1383هـ بطولة المملكة لأندية الدرجة الثانية ويصعد إلى مصاف أندية الدرجة الأولى كان مدرب النصر في ذلك الوقت هو أحمد عبد الله والد اللاعب الدولي الشهير ماجد عبد الله وكان رئيس النادي في تلك المرحلة الهامة في تاريخ النادي هو صاحب السمو الملكي الأمير عبد الرحمن بن سعود بن عبد العزيز والذي لعب للنادي كحارس مرمى فترة من الوقت قبل أن يصبح رئيسا للنادي عام 1381هـ وهو في العشرينات من عمره حيث يستمر في الرئاسة لمدة خمسة وثلاثين عاما ليكون بعدها اقدم رئيس نادي في العالم قبل استقالته عام 1416هـ حيث يعتبر سموه المؤسس الحقيقي للنصر والأب الروحي لكل النصراويين
كانت مرحلة الصعود ووجود صاحب السمو الملكي الأمير عبد الرحمن على كرسي الرئاسة بالنادي هو التأسيس الحقيقي للنصر حيث أختار سموه الجزيرة العربية شعارا لنادي النصر السعودي ومكتوبا بداخلها كلمة نصر كان ذلك عام 1390هـ حيث سجل النصر قبل ذلك في كشوفات وزارة المعارف كنادي رياضي رسمي في عام 1380هـ
ومن ملاعب رملية ومقرات للنادي لم تنشأ أصلا لتكون مقرات لأندية رياضية يبدأ مشوار النصر في تحقيق حلمه بـ اعتلاء قمة الأندية السعودية بقيادة الرئيس الذي لم يدخر جهدا أو مالا ليحقق للنصر حلمه حيث توالت البطولات التي يكون النصر صاحب السبق فيها حتى يصبح للنصر مقره الحديث والواقع بحي العريجاء بمدينة الرياض ويصبح للنصر اسمه على مستوى الأندية العالمية
وخلال هذا التاريخ الحافل بالذهب كان النصر مصنعا للنجوم المشاهير فمن أبو حيدر واحمد الدنيني نجوم السبعينات الهجرية ثم عيد الصغير نجم النصر والمنتخب واللاعب الشهير ماجد عبد الله والكابتن محيسن الجمعان نجم المنتخب في كأس آسيا 84م وهو في السابعة عشر من العمر والحارس الدولي سالم مروان والموسيقار فهد الهريفي وصولا للجيل الجديد من اللاعبين النجوم أمثال إبراهيم ماطر ومحسن الحارثي وغيرهم من النجوم
لم يرتبط اسم النصر فقط بما يقدمه على الساحة من نجوم بل ارتبط اسمه كثير بمن تعاقد معهم النصر خلال تاريخه من مدربين عمالقة مثل البرازيلي زاجالو مدرب البرازيل والفرنسي هنري ميشيل مدرب المنتخب المغربي واليوغسلافي الراحل بروشتش وهو من قدم للنصر لاعبه الكبير ماجد عبد الله كما تعاقد النصر أيضا مع البولندي بوتشنك مدرب بولندا في مونديال 90م وبينيف مدرب بلغاريا في مونديال 94م والبرازيلي سانتانا والفرنسي هيربان بالإضافة للمدرب الفرنسي جان فيرنانديز
كما لعب للنصر اللاعب البلغاري الشهير ستويشكوف في بطولة كأس آسيا للأندية أبطال الكؤوس عام 1998م والتي استضافها النصر بالرياض.