Lensless x-ray microscopy requires the recovery of the phase of the radiation scattered from a specimen. Here, we demonstrate a de novo phase retrieval technique by encapsulating an object in a superfluid helium nanodroplet, which provides both a physical support and an approximate scattering phase for the iterative image reconstruction. The technique is robust, fast-converging, and yields the complex density of the immersed object. Images of xenon clusters embedded in superfluid helium droplets reveal transient configurations of quantum vortices in this fragile system.