A hagyomány szerint a [[Valencia (Spanyolország)|Valencia]] melletti [[Abufera-tó]] nevű édesvízi [[lagúna]] környékén főzték először. Eredetileg [[angolnaAngolnafélék|angolnából]], [[csigák|csigából]] és [[veteménybab|zöldbab]]ból készítették. Egyes szakértők szerint a paella eredetileg sózott [[Tőkehal (gyűjtőnév)|tőkehal]]ból és [[rizs]]ből álló [[böjt]]ös étel volt. Ma a klasszikus ''paella valenciana'' alapját főleg a csirke- vagy nyúlhús adja. Ezt a szárazföld belsejében élő kertészek részesítették előnyben, míg a tenger gyümölcseivel dúsított változatát (''paella marinera'') érthető módon a halászközösségek. Az [[arabok]] által Valencia környékén meghonosított rizs adja az ételbe belekombinált „köretet”. A turisták számára persze igyekeznek minél gazdagabb változatokat az asztalra tenni, minden rendelkezésre álló földi jóval kiegészítve.