«Out from the Deep» es el cuarto y último sencillo publicado por Enigma de su segundo álbum, The Cross of Changes. La carátula era una versión simplificada de la del álbum.

La canción empleaba un formato más tradicional del rock comparado con el distintivo sonido electrónico de Enigma. El motivo musical era muy similar al empleado en el «Dear Prudence» de los Beatles. La canción contenía un sample del tema «The Calling», de Positive Life. «Out from the Deep» estuvo cantado por Michael Cretu.

En el video musical para esta canción —encargado al director venezolano Ángel Gracia (el cual ganó, junto a Cliff Guest, la competición de MTV Make My Video para la canción de Madonna de 1986 «True Blue»)—, un buzo llegaba a una vieja ciudad sumergida parecida a la Atlántida (subrayado por efectos de sonido parecidos a ecos de sonar), y tomaba un paseo por ella, similar al paseo del monje del vídeo musical de «Sadeness (Part I)». Pronto descubría que podía respirar bajo el agua sin escafandra, al tiempo que era atraído por una serie de vívidos murales (pinturas o mosaicos) que combinaban rasgos pompeyanos y bizantinos. El buzo trató de hacer contacto con una de las representaciones murales, una mujer de una extraña belleza. Al ser tocada ésta, todas las figuras volvieron a la vida reanudando presumiblemente lo que eran sus últimas acciones. Pero así también lo hizo el responsable del sino fatal de la ciudad —un Poseidón reminiscente a un enojado Dios de la Capilla Sixtina— recreando de nuevo la catástrofe y el maleficio de la ciudad. Todas las figuras liberadas volvieron a su estado mural anterior. Lamentablemente, el maleficio alcanzó también al buzo.

Todo esto dejaba un mensaje de esperanza: las figuras estaban ahora en unas posiciones diferentes a consecuencia del progreso que habían hecho durante el breve período de tiempo que estuvieron en libertad, y el intrépido buzo había dejado su marca imperecedera, como también un buen mural, para la posteridad. En el fondo musical se repetía por última vez el coro: «That's why we are here» («Por eso estamos aquí»).

• CD maxi sencillo

1. Radio Edit — 4:27
2. Rock Version — 6:44
3. Trance Mix — 5:49
4. Short Radio Edit — 3:30

• Anexo:Discografía de Enigma

• «Out from the Deep» en discogs.com
• «Out from the Deep» en enigmamusic.com