«Kirkegården ved havet» op. 20, er blant dei mest kjende verka til Fartein Valen. Han fekk ideen til stykket under eit opphald på Mallorca i 1933. I den spanske avisa El Sol las han ei omsetjing av diktet Le Cimetière Marin, skriven av franskmannen Paul Valéry.
Avisa kalla dette diktet eit meisterverk i «nutidens og alle tiders diktning» ... som «gir uttrykk for tilværelsens uforanderlighet og livets flyktighet, en meditasjon ved havets bredd på kirkegården i Cette».
Diktet gjorde inntrykk på Valen. I 1947 skreiv han i eit programhefte: «Dette brakte tanken på en annen kirkegård hjemme i Norge, en gammel nedlagt kolerakirkegård like ved sjøen på Vestlandet hvor jeg bor. Musikken følger ikke diktet programmatisk, men søker bare å gi uttrykk for de følelser som vekkes overalt, når mennesket stilles overfor dødens makt».
Kyrkjegarden som Valen hadde i tankane, ligg i utmarka ved Leirvåg, i nærleiken av Valevåg. Den er ein av mange kolerakyrkjegardar i Hordaland, mellom anna i Hystad (Stord) og Møvik (Fjell). Kyrkjegarden ved Leirvåg vart vigsla i 1849 av presten Claus N. H. Daae.
Valen fullførte verket i 1934, og det vart uroppført 16. november same år i Oslo. Verket fekk blanda mottaking i pressa, men dette var Valen godt van med på denne tida. «Fyll programmet med slike moderniteter, og Filharmoniskes tilhørerskare vil skrumpe enda sterkere inn», skreiv Nationen, medan Norges Handels- og Sjøfartstidende meinte at «med Le Cimetière Marin synes Valen å ha skap et av de skjønneste og nobleste verk som er frembrakt i de siste år i noe land».