Klub 1919-cu ildə martın 5-ində yaradılsada rəsmi qeydiyyatdan həmin il 18 Mart tarixində keçmişdir. İlk prezident isə Octavio Augusto Milego Díaz olmuşdur. İlk prezident seçkisi isə qəpik püşkü ilə həyata keçrilmişdir. Klubun ilk oyunu 1919-cu ilin 21 Mayında Valencia Gimnástico komandasına qarşı olub (0-1).

Valensiya 1923-cü ildə Mestalla stadionuna köçdü. Buna qədər isə Yarasalar ev oyunlarını Algirós meydançasında keçirirdi. Mestalladakı ilk oyun Castellón Castaliana qarşı oldu və matç qolsuz heç-heçə ilə yekunlaşdı. Tərəflərin bir gün sonra oynanan oyununda isə Valensiya qələbə qazandı, 1-0. Valensiya 1923-cü ildə Regional Çempionatın qalibi oldu və ilk dəfə İspaniyanın Kral Kuboku uğrunda yarışlara qatılmaq imkanı qazandı.

Yarasalar 1941-ci ildə Kral kuboku yarışlarının finalında Espanyolu məğlub edənə qədər İspaniyadakı vətəndaş müharibəsi klubun inkişafına ziyan vururdu. 1941-1942-ci illər mövsümündə İspaniya çempionluğuna nail olan klub bu uğuru davam etdirərək 1943-1944 və 1946-1947-ci illər mövsümlərində də eyni nəticəni əldə etdi. Baxmayaraq ki, həmin illərdə Kral kubokunda zəfər İspaniya çempionluğundan daha nüfuzlu nailiyyət sayılırdı.

1950-ci illərdə klub ötən onillikdəki uğurları təkrarlaya bilmədi, baxmayaraq ki, artıq bir klub kimi formalaşmışdı. Mestalla stadionundakı yenidənqurma nəticəsində arena 45,000 nəfərlik tutuma sahib olur. Heyətdə artıq yerli və əcnəbi ulduzlar peyda olurdu. Yerli Antonio Puchades və holland hücumçu Faas Wilkes kimi oyunçuları misal göstərmək olar. 1952–1953 mövsümünü ikinci pillədə başa vuran klub növbəti il Kral kubokuna daha bir dəfə sahib çıxdı. Bu ildən sonra Fransisco Franconun şərəfinə yarış Copa del Generalísimo kimi tanınmağa başladı.

Valensiya ilk Avropa səviyyəli uğurunu Beynəlxalq Şəhərlərarası Kubokda qazanıb və bu UEFA Kubokuna qədər keçiriən yarış di. Bu yarışın 1961-1962 mövsümünün finalında Barselonanı məğlub etmişdi. Növbəti mövsümdə də finala qədər yüksələn Yarasalar Xorvatiyanın Dinamo Zaqreb klubuna qalib gəlmişdi. Beynəlxalq Şəhərlərarası Kubokun finalına 3-cü dəfə də yüksələn Valensiya bu dəfə İspaniyalı həmvətənlərinə - Real Zaraqozaya 1-2 hesabı ilə məğlub olur.

Əvvəllər iki dəfə Avropada ilin futbolçusu seçilmiş Alfredo Di Stefano 1970-ci ildə klubun baş məşqçisi təyin edildi və ilk ilindəcə klub 4-cü İspaniya çempionluğuna qovuşdu. Bu da Valensiyaya bir vaxtlar müxtəlif ölkə çempionlarının mübarizə apardığı Avropa Kubokunda iştirak etmək şansı yaratdı. Avropa Kubokunun 1971-1972-ci illər mövsümündə Valensiya 3-cü mərhələdə Macarıstanın Ujpest TE klubuna məğlub olana qədər irəlilədi. 1970-ci illərdə klubun ən məşhur futbolçularından avstriyalı Kurt Jara, holland hücumçu Johnny Rep və argentinalı Mario Kempesin adlarını çəkmək olar. Mario Kempes iki il ardıcıl İspaniya la liqasının ən məhsuldar futbolçusu adına - Pichichi mükafatına layiq görülmüşdü, müvafiq olaraq 1977 və 1978-ci illərdə. Valensiya 1978–1979 mövsümündə Kral Kubokuna və finalda İngiltərənin Arsenalını məğlub etməklə Avropa Kuboklar Kubokuna sahib oldu.

1982-ci ildə klub Milian Milianiçi baş məşqçi vəzifəsinə gətirir. Mövsüm boyu uğursuz nəticələrdən sonra sona yeddi tur qalmış 17-ci yerdə qərarlaşan Valensiyanın baş məşqçisi dəyişdirilir və Koldo Aguirrenin gəlişindən sonra klub həmin il aşağı diviziona düşməkdən qurtulur. 1983-84 və 1984-85-ci il mövsümlərində Visente Tormonun prezidentliyi dövründə klub ağır borclarla üzləşir və 1985-86-cı il mövsümündə maaşları verilməyən futbolçularla komandadaxili psixoloji vəziyyəti pis olan Valensiya 55 illik fasilədən sonra aşağı diviziona düşür.

Arturo Tuzon prezident seçildikdən sonra Alfredo Di Stefano 1986-cı ildə baş məşqçi təyin edilir və klub yenidən la liqaya geri dönür. Di Stefano daha bir il məşqçilik etdikdən sonra klubu tərk edir. Həmin mövsüm Valensiya la liqanı 14-cü yerdə bitirir. Bolqarıstanlı hücumçu Luboslav Penev 1989-cu ildə kluba transfer olunur və klub la liqanı 3-cü yerdə başa vurur. 1991-92-ci il mövsümündə Guus Hiddink baş məşqçi təyin olunur. Bununla da klub ölkə kubokunun 1/4-inə qədər yüksəlir və ölkə çempionatını 4-cü yerdə bitirir. 1992-ci ildə Valensiya FK rəsmi olaraq Məhdud Məsuliyyətli İdman Cəmiyyətinə çevrilir.

1994-cü ildə Braziliya millisi ilə dünya çempionatının qalibi olmuş Karlos Alberto Pereira kluba baş məşqçi təyin olunur. Braziliyalı məşqçi ispan qapıçı Andoni Zubizarreta, rusiyalı hücumçu Oleq Salenko və serb Predraq Miatoviçi öz komandasına qatsa da ona bəslənən etimadı doğrulda bilmir və o Jose Manuel Rielo ilə əvəzlənir. Daha sonralar isə Luis Araqones və Jorge Valdano kimi məşqçilər eləcə də Romario, Klaudio Lopez və Ariel Orteqa kimi ulduz futbolçular da komandanın heyətinə qoşulur.

Valensiya 1999-00 mövsümünə titulla başlayır. Belə ki, Barselonanı məğlub edən "yarasalar" İspaniya Superkubokuna sahib çıxır. Həmin mövsüm Barselona ilə eyni xal toplayan Valensiya yalnız o vaxtki çempion Deportivo La Corunyadan geri qalaraq bürünc medallara sahib çıxır. Amma klubun həmin il ən böyük uğuru tarixində ilk dəfə UEFA Çempionlar Liqasının finalına yüksəlməsi olur. Mayın 24-ü Parisdə oynanılan final matçında Real Madrid öz həmyerlilərini 3-0 hesabı ilə məğlub edir.

Bu həm də Klaudio Lopezin klubdakı vida matçı olur və o, İtalyanın Latsio klubu illə anlaşır. Üstəgəl Farinos Milan İnterinə və Gerard Barselonaya keçir. Həmin mövsümlərarası transfer pəncərəsində norveçli Con Karev, Ruben Baraxa, argentinalı Roberto Ayala, Visente Rodrigez və braziliyalı müdafiəçi Fabio Aurelio kluba transfer olunur. Növbəti qış transfer pəncərəsində Pablo Aimar da komandaya qoşulur. Tezliklə Baraxa, Visente, Ayala və Aimar klubun 2000-ci illərin əvvəlindəki dominantlığında əsas fiqurlara çevrilirlər.

La liqaya əla başlanğıc edən Valensiya 10 oyundan sonra birinci yerdə qərarlaşmışdı. Lakin Çempionlar Liqası kimi ağır turnir klubdan daha çox diqqət tələb edirdi. Beləliklə Hektor Kuperin komandası iki qrup mərhələsini geridə qoyub 1/4 finalda Arsenalı, yarım finalda isə Lids Yunaytedi məğlub edərək finala yüksəlir. Son matçdakı rəqib isə Almaniyanın məşhur Bavariya (Bayern Münxen) klubu olur. Bu klubun ardıcıl iki ildə ikinci Çempionlar Liqası finalı olur. Milanın San Siro stadionunda keçirilən matçda Qaizka Mendieta on bir metrlik cərimə zərbəsindən hesabı açır. Qapıçı Santiaqo Kanizares 90 dəqiqə ərzində Mehmet Şölün penalti zərbəsini qaytarsa da, Ştefan Effenberqin eyni cəhdinə əngəl ola bilmir, 1-1. Əlavə olunmuş iki hissədə də hesab dəyişmədiyindən oyunsonrası penaltilər qalibi müəyyənləşdirdi. Belə ki, Maurisio Pelleqrinin səhvindən sonra Bavariya kuboku başı üzərinə qaldırır. Valensiya üçün ardıcıl iki Çempionlar Liqası finalının heç birində qalib gəlməmək böyük üzüntüyə səbəb olur. Klub həmin uğursuzluqdan sonra özünə gələ bilmir və ölkə çempionatının son turunda Barselonaya son saniyələrdə buraxılan qolla 3-2 məğlub olan "yarasalar" növbəti mövsüm üçün Çempionlar Liqasından kənar qalırlar.

Klubun prezidenti D. Pedro Kortes qazanılan nailiyyətləri - İspaniya Kral Kuboku və iki Çempionlar Liqası finalını - qənaətbəxş sayaraq şəxsi işlərini səbəb gətirib istefa verir. D. Jaime Orti onu əvəzləyərək Valensiyanı Avropada uğurlu klub kimi tanıtdırmağı qarşıya məqsəd qoyur. Tenerifeni aşağı diviziondan la liqaya çıxaran Rafael Benitez baş məşqçi təyin olunur. Heyətindən Mendieta, Deşamp, Milla və Zahoviçi göndərən klub Marçena, Mista, Kurro Torres, Rufete, de los Santos və Salvanı transfer edir.

Valensiya 1999-2004-cü illərdə tarixinin ən uğurlu dönəmini yaşayır. İki dəfə ölkə çempionluğu, bir dəfə UEFA Kuboku, bir dəfə Kral Kuboku və bir dəfə İspaniya Super Kubokuna sahib çıxan klub iki dəfə də Çempionlar Liqasının finalına yüksəlir.

2001-2002 futbol mövsümündə Valensiya 31 illik aradan sonra İspaniya çempionluğuna qovuşur. Baş məşqçi Rafael Benitez və yeni futbolçular Marçena, Mista, Kurro Torres, Rufete, De los Santos və Salvadan ibarət güclü bir komanda yaranmışdı. İlk matçda Valensiya Real Madridi qəbul etdi və bu oyunda qazanılan qələbə klub üçün çox çempionluğa gedən yolda əhəmiyyətli bir təkan oldu. Benitezin komandası sonrakı 11 oyunda da qələbə qazanmaqla Alfredo di Stefanonun 1970-1971-ci ildə əldə etdiyi rekordu təzələdi. Deportivoya məğlubiyyətdən sonra liderlərdən geri qalmamaq üçün Espanyolu səfərdə məğlub etməli olan Valensiya, hesabda 2-0 geridə olmasına baxmayaraq sonradan 3 qol vuraraq qələbə qazandı.

Mövsümün ikinci yarısında Benitezin yetirmələri Real Madridə məğlub olsa da tez toparlanaraq sonrakı 6 oyunda 4 qələbə və 2 heç-heçə edə bildilər. İkinci dövrədəki Espanyol matçı da həlledici oldu. Belə ki hesabda 1-0 geri ikən qırmızı vərəqə ilə azlıqda qalan yarasalar Ruben Baraxanın iki qolu ilə 3 xalı əldə edirlər. Həmin gün Real Madridin Real Sosyedada məğlub olması Valensiyanı liderliyə yüksəldir və ən yaxın izləyicisi Real Madridlə 3 xal fərqi yaranır. Mövsümün son matçı isə Malaqa ilə La Rosaleda stadionunda olur. Ayala və Fabio Aurelionun qolları sayəsində Valensiya tarixində 5-ci dəfə İspaniya çempionluğuna yiyələnir.

Komandanı bəzən "Los Che" adlandırırlar. Bəziləri bunu nədənsə Ernesto Çe Gevara ilə səhvən əlaqələndirirlər, lakin əslində yerli Valensiya dialektində bu, hər hansə şəxsə müraciət formasıdır, məsələn, "ey!" və ya bu sözlə insanlar bir-birini salamlaya bilər. Bu söz Valensiya bölgəsində çox istifadə edilir, buna görə də komandaya da belə ləqəb qoyulub.

Klubun digər məşhur ləqəbi "los murcielagos"dur, yəni "yarasalar". Əslində isə yerli azarkeşlər heç də bu ləqəbdən çox istifadə etmir, daha çox mediya və idman portalları "yarasalar" ləqəbini səsləndirirlər. Komandanın emblemində "yarasa" fiquruna rast gəlmək olar. Bunun bir neçə versiyası var. Biriləri deyir ki, "yarasa" kasıbçılıq simvoludur və tarixən Valensiya şəhəri çox hücumlara məruz qalıb. Digərləri deyir ki, yarasalar sadəcə o bölgədə çox olublar. Bəzilərinə görə isə, XIII əsrdə o bölgədə baş verən müharibə zamanı torpaqlar mavrlardan azad edən kral şəhərə girən zaman bayrağa yarasa oturub, bu da uğur simvolu kimi qəbul edilib. Kral şəhəri ələ keçirdikdən sonra yarasanı şəhərin simvolu kimi bütün bayraqlarda və emblemlərdə istifadə edib.

Çox nadir hallarda, lakin yenə də istifadə edilən köhnə ləqəb "los xotos"dur, yəni "keçilər". Böyük ehtimal, Mestalya stadionu keçilərin yaşadığı və ya məskən saldığı yerdə tikilib. Bəlkə də, "los ches" ilk oyunlarını keçi düzənliklərinə keçirib.