Context. The vortex coronagraph is an optical instrument that precisely removes on-axis starlight allowing for high contrast imaging at small angular separation from the star, a crucial capability for direct detection and characterization of exoplanets and circumstellar disks. Telescopes with aperture obstructions, such as secondary mirrors and spider support structures, require advanced coronagraph designs to provide adequate starlight suppression. Aims. We introduce a phase-only Lyot-plane optic to the vortex coronagraph, which offers improved contrast performance on telescopes with complicated apertures. Potential solutions for the European Extremely Large Telescope (E-ELT) are described. Methods. Adding a Lyot-plane phase mask relocates residual starlight away from a region of the image plane, thereby reducing stellar noise and improving sensitivity to off-axis companions. The phase mask is calculated using an iterative phase retrieval algorithm. Results. Numerically, we achieve a contrast on the order of 10-6 for a companion with angular displacement as small as 4λ/D with an E-ELT type aperture. Even in the presence of aberrations, improved performance is expected compared to either a conventional vortex coronagraph or an optimized pupil plane phase element alone.