«Насьональ» из Монтевидео — первый южноамериканский клуб, основанный не англичанами, живущими и работающими в странах континента, а самими уругвайцами. Поэтому и название он получил «Насьональ».
В ранней истории клуба случился даже эпизод, когда «Насьональ» выступил в роли сборной своей страны, сыграв товарищеский матч со сборной Аргентины, и одержал победу со счетом 3:2. Тогда шел 1903 год. В том же году «Насьональ» во второй раз стал чемпионом Уругвая. И уже тогда определился его главный и непримиримый соперник — столичный «Пеньяроль». Соперничество с переменным успехом не прекращается до сих пор. Начавшись в национальном первенстве Уругвая, с 1960-х годов оно вышло и за его рамки — в международные турниры.
В чемпионатах страны самым успешным для «Насьоналя» было пятилетие с 1939 по 1943 год. Тогда клуб побеждал 5 раз подряд, причем 8 декабря 1940 года разгромил своего злейшего врага со счетом 8:0. В те годы линия нападения «Насьоналя» не знала себе равных, — правда, главной ударной силой был тогда не кто-либо из футболистов-уругвайцев, а аргентинский легионер Аттилио Гарсия, пришедший из клуба «Бока Хуниорс». Начиная с 1938 по 1946 год, Гарсия раз за разом становился лучшим бомбардиром Уругвая, лишь в 1945 году уступив первое место другому футболисту. Всего же за свою карьеру Гарсия забил 486 голов — 34 из них в ворота «Пеньяроля». В матче, выигранном у «Пеньяроля» со счетом 8:0, половина мячей была на счету Гарсии.
Увы, уже в те времена «Насьоналю», как и другим сильнейшим южноамериканским клубам, приходилось терять собственных талантливых футболистов, уезжавших в Европу. В начале 30-х годов, например, в миланский «Интер» перебрался Эктор Скароне, чемпион мира 1930 года в составе сборной Уругвая. В 1934 году он, правда, вернулся в родной клуб, но ненадолго. В 1950-е – 1960-е годы лучшие футболисты уругвайских клубов, в том числе «Насьоналя», стали уезжать в другие страны еще чаше.
Как бы то ни было, непримиримое соперничество «Насьоналя» с «Пеньяролем» продолжалось. Несмотря на некоторые громкие победы «Насьоналя» над главным соперником, тот по числу выигранных чемпионских титулов если порой и отставал, то ненадолго, а потом выправлял положение и сам оставлял «Насьональ» позади. В конце концов, «Пеньяроль» медленно, но верно стал выходить вперед…
К огорчению поклонников «Насьоналя», именно «Пеньяроль» стал первым южноамериканским клубом, выигравшим Кубок Либертадорес, да еще дважды подряд. В 1966 году «Пеньяроль» завоевал уже свой третий Кубок Либертадорес и прибавил к нему второй Межконтинентальный кубок. «Насьональ» же в эти 1960-е годы трижды терпел в финальных матчах Кубка Либертадорес поражения от аргентинских клубов «Индепендьенте», «Расинг» и «Эстудиантес».
Но в 1971 году первую победу в Кубке Либертадорес праздновал наконец и «Насьональ». Именно ему удалось остановить аргентинский «Эстудиантес», выигрывавший тогда клубный чемпионат Южной Америки трижды подряд, причем не особо стесняясь в средствах, за счет даже не жесткой, а жестокой игры. Победа далась «Насьоналю» трудно — первый финальный матч он проиграл — 1:0, второй выиграл с таким же счетом. В дополнительном матче два сухих мяча, забитых Виктором Эспараго и аргентинским легионером «Насьоналя» Луисом Артиме, принесли победу уругвайскому клубу. Артиме, забив 10 мячей, стал к тому же лучшим бомбардиром Кубка Либертадорес 1971 года.
Он же был автором двух мячей из трех, забитых в том же году «Насьоналем» в матчах за Межконтинентальный кубок. Тогда амстердамский «Аякс», победитель Кубка европейских чемпионов, отказался сражаться за этот трофей, и Европу представлял второй финалист — греческий «Панатинаикос». Матч в Афинах закончился вничью — 1:1, в Монтевидео выиграл «Насьональ» — 2:1.
В последующие годы у «Насьоналя» был стопроцентный результат: он еще дважды выходил в финал Кубка Либертадорес и оба раза завоевывал трофей. В 1980 году уругвайский клуб победил бразильский «Интернасьонал». Все решил единственный мяч, забитый во второй игре Вальдемаром Викторино (первая закончилась нулевой ничьей). 11 февраля 1981 года в Токио Викторино вновь забил единственный гол, принесший «Насьоналю» победу над английским клубом «Ноттингем Форест» в Межконтинентальном кубке.