Клуб был основан в 1919 году двумя друзьями, отдыхавшими в местном баре. Чтобы решить, кто будет президентом, пришлось бросать монетку — жребий пал на Октавио Аугусто Милего Диаса. 21 мая того же года состоялся первый матч новой команды, закончившийся поражением 0:1 от «Химнастико». На стадион «Месталья», обладавший поначалу только одной трибуной, «Валенсия» переехала в 1923 году. Тогда же клуб выиграл региональный турнир, впервые добился права участия в Королевском Кубке и пригласил чешского тренера Антона Фивбера.

В сезоне-1928/29 «Валенсия» начала выступать в объединенном чемпионате Испании, поначалу в во второй лиге, а с 1931 года — и в высшей. После перерыва, вызванного гражданской войной, «Валенсия» оказалась в числе наиболее сильных клубов Испании. В1941 году она выигрывает кубок (тогда называвшийся Кубком Генералиссимуса), а на следующий год становится чемпионом страны. До конца 40-х «Валенсия» еще дважды выиграет чемпионат и однажды — Кубок.

В 50-е и 60-е годы на внутренней арене клуб выглядел не так убедительно, зато три года подряд играл в финале Кубка Ярмарок, выиграв его в сезонах 1961/62 и 1962/63. Новый взлет случился в сезоне-1970/71, когда под руководством Альфредо Ди Стефано «Валенсия» смогла выиграть чемпионат Испании. Команда, имевшая в составе Курта Яру и Марио Кемпеса, была реальной силой на протяжении 70-х годов и в сезоне-1979/80 выиграла Кубок Обладателей Кубков и Суперкубок Европы.

После трудного начала 80-х, когда «Валенсия» даже на год вылетала из высшего дивизиона, клуб постепенно стал возвращаться в элиту испанского футбола. Под руководством Клаудио Раньери команда выиграла в 1999 году Кубок страны, а сменивший его Эктор Купер два года подряд выводил «Валенсию» в финал Лиги чемпионов. Рафаэль Бенитес смог дважды выиграть в сезонах 2001/02 и 2003/04 чемпионат Испании, а также завоевал в 2004 году Кубок УЕФА.

После тяжелого, полного скандалов сезона-2007/08 (светлым моментом стал выигрыш Королевского кубка), команду возглавил молодой баскский специалист Унай Эмери.

Наиболее известное прозвище клуба — «летучие мыши»; соответствующее животное изображено на эмблеме «Валенсии», куда перешло с герба города. По легенде, когда король Хайме I Арагонский отвоевывал Валенсию у мавров, летучая мышь села на флагшток его штандарта, и монарх воспринял это как добрый знак небес.