Walencja jest uważana za kolebkę paelli. Można więc spróbować tej smacznej potrawy w wielu restauracjach w mieście. Jeden z najbardziej znanych miejsc to Restaurante La Pepica, gdzie paella była podawana już od 1898 roku. Inne popularne miejsca to Restaurante Levante i Restaurante Casa Carmela.