Početak Valencia CF osnovana je godine 1919. u istoimenom gradu. Prvi predsjednik kluba bio je Octavio Augusto Milego Díaz koji je izabran je nasumce; točnije bacanjem novčića u zrak, jer se vodila neizvjesna bitka između njega i Gonzala Medine Pernáesa. U početku, Milego i Medina radili su zajedno malom poduzeću u ulici Barcelona, koje je bilo i ujedno sjedište kluba. Tu se nalazio i prvi Valencijin Upravni odbor, u kojem su bili braća Pascual i Julio Gascó, Andrés Bonilla, José Llorca, Fernando Marzal i Adolfo Moya.

Međutim, uz neivjesnu političku situaciju u zemlji, ni društvo ni mediji nisu bili previše zainteresirani za novi nogometni klub. Nogomet se u gradu igrao i prije osnivanja Valencie CF, već 1908. bilo je nekoliko momčadi kao što su Levante, Gimnástico i Hispania. Činilo se da je nogomet stigao u Valenciju preko poslovnih ljudi koji uvoze i izvoze proizvode iz Velike Britanije, kolijevke nogometa. Često su se u Valencijinim lukama mogli vidjeti britanske mornare kako igraju nogomet s časncima. Svoj prvi susret Valencia je igrala daleko od kuće. Igrali su u mjestu Castellón, dana 21. svibnja 1919. Valencia je igrala protiv svojih gradskih rivala Gimnástica, koje su pobijedili rezultatom 1:0. Prva momčad Valencie je ovako izgledala: Marco, Peris, Julio Gascó, Marzal, Llobet, Ferré, Fernández, Umbert, Martineza, Ibarra, Aliaga i Gómez Juaneda.

Valencijin prvi stadion bio je Algirós, otvoren 7. prosinca 1919. Algirós je služio za sve susrete Valencijine momčadi do 1923., kada su se preselili na Mestallu. Valencijin prvi susret na Mestalle je završio rezultatom 0:0, protiv Castellón Castalie. Obje momčadi su opet igrale sljedeći dan, a Valencia je pobijedila s 1:0. Malo po malo, raslo je zanimanje za utakmice Valencie, te se stadion Algirós počeo proširivati. Kako bi pokrili troškove, uprava je počela naplaćivati ulaznice, koje su prodavane za 25 centi.

Početkom 1920-ih godina, počelo se je održavati Regionalno prvenstvo između nekoliko momčadi, gdje se kod tih momčadi javlja natjecateljski duh, koji je donio pravu atmosferu na stadione. Valencija je 1923. po prvi puta postala regionalni prvak, a tim je uspjehom dobila pravo sudjelovanja u Španjolskom kupu. Rezultati kluba pokazivali su mogućnost velikog napretka, kojim bi bili vrlo uspješna momčad unutar Španjolske. Nakon nekoliko godina nakon svog osnutka, Valencija je bila vrlo moćna momčad tako da nisu, kod ostalih momčadi bili omiljeni. Momčad Valencije je značajno ojačana kada su htjeli doveli vrlo dobre igrače poput Montesa ili Cubellsa, ako žele napraviti nešto više od igranja u Reginalnoj Ligi. Valencijini navijači su se rascijepali na dva dijela jedan dio je za jednog igrača, a drugi dio za drugog igrača, slično kao borba s bikovima: s jedne strane, tu su bili cubellistas, i na drugoj strani, montistas. Na kraju su i jedan i drugi igrali za Valenciju. Takvo nadmetanje je bilo dobro za momčad, jer jednom i drugom igraču je bilo igrati u čast: braniti boje Valencia Club de Fútbol. Arturo Montesinos, Montes, zbog njegovih fizičkih karakteristika (bio je visok 1,90 m), bio je agresivniji igrač od Cubellsa. Eduardo Cubells, bio je puno više, nego tehnički naobrazovan igrača, bio je prvi međunarodni igrač koji je igrao za Valenciju. Povratkom u natjecanje Copa del Rey gdje je Valencia prvi puta sudjelovala, cijeli grad je bio uzubuđen, protivnici su bili Sporting de Gijón. Prva utakmica se je igrala na stadionu Algirós, na prepunom stadionu. Rezultat je završio s 1:0 za Valenciju, a pogodak je zabio Montes. Mjesec dana kasnije, na uzvratnom susretu u Gijónu Valencija je doživjela težak poraz od čak 6:1, po tadašnjim pravilima igrala se je treća utakmica, koja se je održala u Oviedu, u kojoj je Valencija izgubila s 2:0. Unatoč porazu, Valencijina je prednost i činjenica u tome da su odigrali još jednu utakmicu na domaćoj razini, jer se je broj pristalice "Che" povećao. Ovo progresivno povećanje interesa u Valenciji, je rezultiralo tome da je Valencijino rukovodstvo, moralo početi tražiti zemlju koja je na prodaju, za izgradnju novog stadiona. Našli su ga pokraj samog Mestalla kanala za navodnjavanje.

Mestalla i Valencia - promocija mini|desno|300px|Momčad Valencije 1927. Ramón Leonarte tadašnji predsjednik Valencije je potpisao ugovor za kupnju zemlje u kojoj je Mestalla u vlasništvu kluba do siječnja 1923. Cijena zemlje je stajala 316,439 pesetas, otprilike 2 eura, za današnje vrijeme, a u to vrijeme to je bila značajna količina novca. Stadion bi otprilike imao 17,000 gledatelja, a projekt su dobila dva čovjeka: arhitekt je bio Francisco Almenar, budući predsjednik, i graditelj Ramón Ferré, također član kluba.

Otvaranju novog stadiona se je odvijao 20. svibnja, 1923., a gostujuća momčad je Levante UD. Konačni rezultat je bio 1:0 za Valenciju, a prvi igrač koji je imao čast da zabije pogodak na mestalli bio je Montes. Tjedan dana kasnije, škotska momčad Dundee United, gostovala je na Mestalli. Oni su odigrali dva susreta u dva dana u kojima je oba puta Dundee pobijedio s rezultatima 0:3 i 0:1. Do 1923., nogometni trener praktički nije ni postojao. Sve do početka sezone 1923. – 24. kada je klub unajmio jednog češkog trenera Antona Fivbera, koji je klubu s Mestalle dao međunarodni prestiž. Trener je dobro radio svoj posao, a imao vrlo dobru ulogu u promoviranju mladih igrača, u pravom trenutku kada profesionalnost malo pomalo počinje dominirati sportom.

U to vrijeme, je počelo stvaranje domaće lige koja će uključivati najbolje momčadi u zemlji, koja će promovirati Španjolsku. Valencijin cilj je bio sudjelovati u takvoj ligi, međutim kako su oni bili mlada momčad i mali klub i tek stvarali svoju momčadi, uz to nisu imali veliki plan i program rada, bili su prisiljeni čekati tri godine prije nego što su mogli činiti dijelom prva liga. Na kraju 20. stoljeća u Valenciju stiže Luis Colina, koji je u klubu radio kao tehnički tajnik u razdoblju od 1928. do 1956. Njegov rad je uvelike bio bitan za uspostavu i uspjehe kluba. Osim stvaranja mlađih kategorija Valencije, Colina je bio poznat kao vrlo dobar skaut, koji je doveo vrlo dobre igrače u klub. Liga je podijeljena na dvije lige. Prva liga sačinjavala je šest puta pobjednike Copa del Rey: Athletic Bilbao, Real Madrid, F.C. Barcelona, Real Sociedad, Real Unión de Irún and Arenas Getxo. Pridružili su im se tri puta finalisti tog natjecanja, Atlético de Madrid, Español i Europa. Ukupno je bilo devet momčadi i bilo je potreban još samo jedan klub da se upotpuni liga od 10 klubova. Održavao se je turnir između klubova: Valencija, Real Betisa, Seville i Racing de Santandera. Kantabrijski klub, je dobio pravo igranja u prvoj ligi, dok je Valencija igrala u drugoj ligi.

Valencija je u drugoj ligi zaigrala u sezoni 1928. – 29., au tom društvu su se nalazili: Sevilla F.C., Iberia Zaragoza, Deportivo Alavés, Sporting de Gijón, Valencia, Real Betis, Real Oviedo, Deportivo de La Coruña, Celta Vigo i Racing Madrid. Povijesni debi se je dogodio 17. veljače 1929. na Mestalli, s Oviedom. Valencija je taj susret pobijedila s 4:2,a u toj momčadi su igrali: Pedret, Torregaray, Moliné, Salvador, Molina, Amorós, Pérez, Imossi, Navarro, Silvino and Sánchez. Imossi i Navarro su zabili po jedan gol, dok je Silvino zabio dva gola.

U svojoj trećoj sezoni u drugoj ligi, Valencija je dobila promociju u prvu ligu. To je bila sezona 1930. – 31., na čelu s trenerom Fivberom pokazali su veliku superiornost i snagu. Nogometaša koji su zajedno s klubom dobili promociju bili su Cano, Villarroya, Conde I, Melenchón, Torregaray, Pasarín, Torres, Amorós, Arilla, Conde II, Imossi, Molina, Salvador, Costa, Navarro, Octavio, Perona, Picolín, Ricart, Rino, Sánchez, Torredeflot i Vilanova. Ovom promocijom završena je prva faza u klubu i otvorena druga puna slave i pobjede. Nakon pet sezona provedenih u prvoj ligi, došlo je do prekida natjecanja zbog Španjolskog građanskog rata

1940-ih Nakon građanskog rata 1936., Valencija se je morala prilagoditi na novu realnost. Mnogi nogometaši koji su igrali za klub, napustili su ubrzo "che" momčad. Vojska se je također umiješala u nogometu, kao što se je umješala i druge aspekte svakodnevnog života. U lipnju 1939., Alfredo Gimenez Buesa je imenovan za predsjednika, a Luis Casanova za potpredsjednika kluba.

Poduzetni period

Valencijini koraci u Europi

Alfredo di Stefano - period U travnju 1970, Alfredo Di Stefano je došao u Valenciju. U teškim vremenima za klub s Mestalle, zamijenio je na klupi Enrique Buqué i Artigas Salvadora. U toj sezoni, Valencija je finalu u Barceloni izgubila od Real Madrida (3:1). Montjuïc je za Valenciju bio stadion favorita i sve je bilo na njihovoj strani: Madrid je igrao jednu od najgorih sezona u svojoj povijesti, a uz to na poluvremenu su im bili ozljeđeni Grosso i Amancio, ali usprkos svemu, Madrid je slavio u finalu.

U prvoj sezoni što je Di Stefano vodio momčad, ta sezona je bila jedna od najuzbudljivijih i naiščekivanijih u povijesti Valencije. Di Stefano je stvorio novu momčad, pouzdanu i jaku u obrani s igračima poput Sola, Aníbal, Jesús Martíneza i Antona, kojima je pomagao odličan vratar Abelardo. Pametan i brz nogomet koji se igrao u veznom redu, nagovještavao je igrače pout José Claramunta; koji je bio okretan i brz napadač, savršen za kontranapade s Formentom, Valdezom, Sergiom i Pellicerom koji su tada bili ključni igrači momčadi.

Sezona 1970./1971, je posljednja sezona u kojoj je sudjelovalo 16 momčadi, a već nakon prvog kola Valencia se je nalazila u opasnoj poziciji iz koje je mogla ispasti u drugu ligu, no malo pomalo Valencijini rezultati su se poboljšavali, a Valencija se je učvrstila u sredini tablice. Velika utakmica prvenstva igrana je na Nou Campu, Valencija je tukla Barcelonu 2:0, s pogodcima Claramunta i Valdeza, a Abelardo je kasnije obranio jedanaesterac. Za Valenciju je to bio snažan poticaj koji ih je gurnuo u borbu za naslov.

Najvažniji u toj sezoni zapamtili smo posljednju utakmicu koja se je igrala protiv Espanyola. Valencija je tada predvodila tablicu s 43 boda, dok su Barcelona i Atlético Madrid, imali 42 odnosno 41 bod. Di Stefanova momčad je trebala jedan bod za naslov prvaka, ali ga nisu osvojili jer ih je Españyol pobijedio s 1:0. No kako je Barcelona remizirala i imala jednak broj bodova kao Valencija, odlučivao je međusobni ogled u kojem je Valencija bila bolja, a titula prvaka otišla je na Mestallu. Mnogi analitičari su se složili da je Valencijina četvrta titula prvaka bila plod solidne obrane na čelu s odličnim vratarom Abelardom.

Nakon što je završila ligaška sezona, Valencija se je okrenula kupu, gdje je stigla do finala uvjerena da mi mogla uzeti dvostruku krunu. "Che" momčad je stigla u finale tako što je eliminirala Mallorcu, Betis, Málagu i u polufinalu, Sevillu. Do finala su bez izgubljene utakmice, a uz to su zabili osamnaest pogodaka u osam susreta. Igralo se je na Santiago Bernabéu, a protivnik im je bila Barcelona. Pobjeda je otišla na stranu katalonske momčadi koja je u jednoj odličnoj utakmici pobijedila Valenciju s 4:3. Valencia nije mogao doći do vrha u jednoj od najboljih sezona u svojoj povijesti.

Osvajanjem ligaškog naslova, dalo im je priliku da debitiraju u Europskom kupu, u najvišem natjecanju europskog nogometa. Valencija se je brzo oprostila od natjecanja, iako su pobijedili Luxemburgo i Hajduk Split, ispali su trećem kolu od mađarskog Újpesti Dózsa.

Iako je ova momčad Valencije bila bolja od one koja je osvojila ligaški naslov, sezonu 1971./72. završili su na drugom mjestu. Valencija je bila trenutni prvak i sve momčadi su se ugledali na njih. Pojačanjima poput Quina, Adorna i Lica poboljšale su se mogućnosti momčadi, premda ni to nije bilo dovoljno da ponove prošlogodišnju sezonu u kojoj je prvak bio Real Madrid.