這支足球隊的第一任主席的推舉，居然由一枚硬幣來決定，Octavio Augusto Milego Díaz及Gonzalo Medina Pernás都有資格出任主席，他們決定拋一枚硬幣，以落地後的正反面來決定主席職位的誰屬。最後 Octavio Augusto Milego Díaz 幸運地勝出。但他們還像以前一樣，沒有傾軋與妒忌，肩並肩地在 la calle Barcelonina 上一間房子裡一起工作，承擔起這所新俱樂部的事業。瓦倫西亞就是這樣的誕生。第一年的瓦倫西亞管理層還有他們： Pascual 兄弟，Julio Gascó，Andrés Bonilla，José Llorca，Fernando Marzal 和 Adolfo Moya。
不過，瓦倫西亞的成立，無論在社會上，或是在媒體上，都沒有任何反響。由於社會上政治局勢，西班牙正處於不確定的時代，當時的報紙難以處理體育新聞。在瓦倫西亞成立之前，這城市裡已經存在幾間俱樂部，但他們都沒有主導瓦倫西亞的足球。1908年，這裡已經有幾個俱樂部在瓦倫西亞大區：萊萬特， Real Gimnástico ， Hispania 或 Hispano 。
毫無疑問，當時的瓦倫西亞是支偉大的隊伍，至少被稱為是在當時世界上最好的球隊之一，擁有 Ignacio Eizaguirre 作為門將，由兩個非常了解對方的後衛， Álvaro and Juan Ramón 來負責中路防守，還有一條由兩個瓦倫西亞人和三個巴斯克人組成的“閃電鋒線”。這支隊伍為俱樂部奪得了第一個全國錦標：1941年的西班牙國王杯。這是這支無敵之師開始其20年輝煌歷史的第一個戰利品，可以想像在圖利亞河首府的慶祝活動有多么盛大。贏得獎盃，聯賽排名第三，擁有數名國際級球員，這使得瓦倫西亞在西班牙迅速躋身成為“大俱樂部”的行列。
1941年西班牙國王杯
當1941/42賽季俱樂部贏得歷史上第一個西班牙聯賽冠軍時，梅斯塔利亞的輝煌達到頂點。不過諷刺的是，當時的杯賽居然比聯賽更重要。不過就算是這樣，瓦倫西亞的那個賽季依然讓人熱血沸騰。球隊不僅刷新了聯賽的進球記錄（26場比賽進85球），而梅斯塔利亞更成為了無懈可擊的堡壘。（只有 Atlético Aviación 在瓦倫西亞主場取得過勝利），瓦倫西亞變成了一支無堅不摧的超級勁旅。當時隊中的前鋒，Edmundo，更是以27個進球成為該賽季的最佳射手。
經歷了一個賽季的沉默，在1943/44賽季，瓦倫西亞再次登上聯賽冠軍的寶座。這一次，瓦倫西亞是從聯賽開始便一直領跑積分榜，而只有巴塞隆納曾在聯賽中以4:3擊敗過主場的瓦倫西亞。 Mundo 又一次以27個進球高居射手榜首位。瓦倫西亞在聯賽中的優勢太過明顯以至於人們都開始忽視聯賽的存在，不過瓦倫西亞的球迷們沒有理由不高興，看著自己的隊伍在4年內捧起了第3座獎盃。
在40年代，瓦倫西亞也並不是一帆風順。事實上，瓦倫西亞是一支連續三次進入西班牙杯賽決賽都飲恨的西班牙球隊。在1944、1945和1946年連續三屆杯賽，瓦倫西亞都功虧一簣取得亞軍。這次連續的決賽失利被認為是受到了嫉妒的詛咒，因為那三場決賽都是在同一場地上進行的—— Estadi Olímpic de Montjuïc。這座位於巴塞隆納的球場被瓦倫西亞球迷稱為不祥之地。第一年，瓦倫西亞在這裡以0:2不敵畢爾巴鄂競技，第二年瓦倫西亞2:3再次被巴斯克雄師絆倒，第三年皇家馬德里以3:1讓瓦倫西亞人再次流下傷心的眼淚。
1946/47賽季，瓦倫西亞第三次成為聯賽冠軍，而當時，真正意義上的足球場開始與體育場開始區別開來。瓦倫西亞在那個賽季的奪冠路程可謂跌宕起伏。球隊在聯賽開始時的表現非常糟糕，8輪比賽過後，瓦倫西亞僅比聯賽墊底的隊伍高 2分。但到了聯賽的最後一輪，聯賽冠軍到底花落誰家仍然未有答案。所有人都看好畢爾巴鄂奪冠，但馬德里競技（原名 Atlético Aviación ，1947年一月改名馬德里競技）和瓦倫西亞都還有機會。在最後一場聯賽中，Pasarín 的瓦倫西亞以6:0擊敗了皇家希洪競技，而他的對手卻都停下了前進的腳步。畢爾巴鄂競技3:3戰平拉科魯尼亞，而馬德里競技則被自己永遠的敵人皇家馬德里2:3擊敗。憑藉與畢爾巴鄂的對賽優勢，以及在聯賽兩回合比賽中，因為無論在聖馬梅西球場還是梅斯塔利亞球場都擊敗了對手。瓦倫西亞奇蹟般中再次舉起聯賽冠軍獎盃。在沒有電子記分牌也沒有無線電廣播的年代裡，是從電話里得知瓦倫西亞贏得第三次聯賽冠軍的喜訊。
在1961年7月2日，整個瓦倫西亞市沉浸在憂傷中，巴西人 Walter 在通往 El Saler 的道路上遇上交通意外死亡。這時，俱樂部的主席 Julio de Miguel Martínez de Bujanda 在接下來的時間裡開創了瓦倫西亞歷史上一個輝煌的10年。同時在這個時候，西班牙足球有了一個新的挑戰：參加歐洲賽事，向其他歐洲列強證明自己的實力。
Julio de Miguel 取得的第一個錦標就是城市博覽會杯冠軍。這項比賽的參賽權需由比賽委員會的邀請，而並不是由聯賽中的成積而決定。當時 Julio de Miguel 成功簽下一名偉大的球員——巴西人 Waldo Machado ，他在梅斯塔利亞給球迷留下了無數個激情的夜晚，並且是俱樂部歷史上的頂級射手之一。他的自由球，他那令人難以置信的打門，還有他的快樂足球，都在西班牙及歐洲大陸留下了不可磨滅的印記。 Waldo 的最佳拍檔就是 Vicente Guillot， Vicente 給巴西人的傳球總是恰到好處，在球場上他們似乎閉上眼睛都可以找到對方。伴隨著瓦倫西亞在歐洲成功是在聯賽中平庸表現。
1962/63賽季，作為城市博覽會杯的衛冕冠軍身份，瓦倫西亞在接下來的一個賽季里成功衛冕。在衛冕的征途上，第一個障礙是3支蘇格蘭的球隊：凱爾特人、鄧弗姆林和喜百年。在四強，瓦倫西亞將面對羅馬，在梅斯塔利亞，瓦倫西亞乾淨利落的以3:0取勝，但在客場奧林匹高球場，瓦倫西亞僅以0:1落敗，但是瓦倫西亞還是順利拿到了進軍決賽的入場券。決賽中的對手是薩格勒布戴拿模。首回合的比賽在南斯拉夫城市薩格勒布舉行，瓦倫西亞開賽不久便落後了，但是多虧了 Waldo 和 José Antonio Urtiaga，他們為瓦倫西亞追成平手。次回合比賽於1963年6月26日在梅斯塔利亞舉行，50.000位觀眾見證瓦倫西亞在本場比賽中的精彩表現，他們以2:0擊敗這支來自巴爾幹的球隊，Mañó 和 Héctor Núñez 分別建功。
在接下來的一個賽季，瓦倫西亞再一次打入城市博覽會杯決賽。在打敗愛爾蘭的沙姆洛克流浪、奧地利的維也納迅速和匈牙利烏派斯，之後的四強里，瓦倫西亞遇上了德國科隆，球員費了一番努力才能打敗德國人。另一支西班牙球隊——薩拉戈薩正在等待決賽中與瓦倫西亞對決(此屆決賽場地為中立場諾坎普體育場，採用一回合賽制)，這次的結果與前兩次不同，勝利是屬於來自阿拉貢地區的球隊，他們憑藉著 Villa 和 Marcelina 的兩個進球以2:1的賽果捧起了冠軍獎盃， Urtiaga 為瓦倫西亞扳回一分。決賽受挫於薩拉戈薩是一次沉重的打擊，此後的三年瓦倫西亞一度沉默了。
這一切都在1967年6月得到改變，一項新的桂冠降臨梅斯塔利亞，不過這一次獎盃換成了西班牙國王杯。瓦倫西亞一直保持著球隊的新陳代謝。這次輪到了 Juan Cruz Sol 和 Pepe Claramunt ，這兩位關鍵球員的加盟，幫助瓦倫西亞再次在西班牙足壇占上重要位置。還有依靠 Waldo，澳洲守門員 Abelardo，瓦倫西亞打入了1967年的西班牙杯決賽。晉級決賽的道路是漫長而艱難的，在輕鬆擊敗首兩輪的對手卡迪斯和皇家貝蒂斯之後，在八強瓦倫西亞殺退了傳統勁旅皇家馬德里，並在四強遇上另一支來自瓦倫西亞自治區的球隊埃爾切，決賽面對的是另一個老對手：畢爾巴鄂競技。決賽在首都馬德里舉行，依靠 Paraguayan Anastasio Jara 和 Paquito 的進球，瓦倫西亞擊敗了巴斯克對手， Roberto Gil 舉起了球隊歷史上的第四座西班牙國王杯，這座新的獎盃對於渴望榮譽的瓦倫西亞球迷無疑是一份最好的禮物。
