Composed of på, hav and bund. The inflection havsens is a fossilized singular genitive definite form.
på havsens bund (literally, “on the bottom of the sea”)