Brendan i Lisa długo zastanawiali się nad tym, jak powinien wyglądać kolejny album DCD, zwłaszcza, że wspomniane zmiany w ich życiu prywatnym bardzo utrudniły ich współpracę. Jak sami później przyznawali, finalny album to coś w rodzaju kompromisu pomiędzy dwiema zupełnie odmiennymi koncepcjami. Brendan skłaniał się ku bardziej klasycznym formom muzycznym z wykorzystaniem klasycznych instrumentów i angielskimi tekstami, podczas gdy Lisa komponowała wiele utworów będących wynikiem jej fascynacji muzyką etniczną, a zwłaszcza grecką. - Nie widzimy się ze sobą już dwa lata i komponujemy oddzielnie z zamiarem spotkania się wyłącznie na czas nagrania albumu – mówiła Lisa w trakcie prac nad płytą. Co prawda muzycy pozostawali w kontakcie ze sobą, ale ich wzajemny wpływ na tworzone przez siebie utwory był raczej znikomy.

W tym czasie powstało bardzo wiele utworów, spośród których większość nigdy nie doczekała się nagrań studyjnych (niektóre znamy choćby z wydanego później albumu koncertowego „Toward The Within”). - Jest tak wiele utworów, których nie zamierzam nigdy nagrywać – wyjaśniała Lisa. - Byłoby to dla mnie jak uwięzienie ich w ściśle określonej formie bez możliwości późniejszych zmian. Chciałam za to pozwolić, by niektóre utwory wciąż ewoluowały i oddawały stan, w którym znajduję się w danym etapie swojej muzycznej drogi.

Spośród utworów przygotowywanych z myślą o nagraniu w studio wybrano w sumie jedenaście, z czego aż siedem to kompozycje Lisy. Brendan – mimo iż wciąż posiadający ostateczną moc decyzyjną – postanowił „oddać” większość miejsca jej utworom, będąc powodowanym chęcią zachowania pewnej spójności płyty, na tyle, na ile dało się ją uzyskać. Tym spoiwem, elementem przewijającym się przez większość utworów, była mitologia grecka, a zwłaszcza mit o Tezeuszu. Odnosi się do niego już sam tytuł albumu: „Into The Labyrinth” („W labiryncie”). Motywy tej opowieści przewijają się w sumie przez pięć utworów: „Ariadne”, „Towards The Within”, „The Spider's Stratagem” i „Emmeleia”. Znalazło się też miejsce na inspirowany kulturą aborygeńską utwór „Yulunga” oraz irlandzką balladę „The Wind That Shakes the Barley" autorstwa dziewiętnastowiecznego poety Roberta Dwyera Joyce'a, nawiązującą do rewolucji irlandzkiej z końca XVIII wieku.
Ten stylistyczny i treściowy miszmasz poszerzały cztery kompozycje Brendana, bardzo odmienne od pozostałych zarówno pod względem tematu, jak i stylu. Pierwszy z nich to „The Ubiquitous Mr Lovegrove”, którego bohaterem jest – jak przyznaje sam artysta – alter ego Brendana, opowiada, jak sam wyjaśnia, o „abstrakcyjnej relacji pomiędzy nim a kobietą”. Co ciekawe, rok później utwór ten został wykorzystany w filmie „Obsesja” Seanna Penna. Kolejny to „The Carnival Is Over”, na który składają się młodzieńcze wspomnienia artysty związane z wizytą w cyrku (chyba „najlżejszy” utwór DCD w karierze). Znalazło się też miejsce na komentarz społeczny w utworze „Tell Me About the Forest”, o którego przesłaniu Brendan Perry mówił: Kiedy mieszkasz w Irlandii widzisz ludzi, którzy po wielu latach nieobecności powracają do swoich rodziców, widzisz też tych, o których zapomnieli... złamanie tradycji razem z wykorzenieniem i przewrotem plemiennym. To samo w Irlandii i to samo w lasach tropikalnych. Gdybyśmy mogli podtrzymać tylko ustną tradycję...
Album zwieńczono najdłuższym, bo ponad dziewięciominutowym utworem „How Fortunate the Man with None” będącym adaptacją wiersza niemieckiego poety Bertolta Brechta, znanego ze swojego społecznego zaangażowania i buntowniczego przesłania swoich utworów.
Co ciekawe, o ile Brendan śpiewał w języku angielskim, Lisa opierała swój wokal wyłącznie na glosolalii, rezygnując z wykorzystania jakiegokolwiek istniejącego języka.

Na nagrania Lisa przyjechała do nowej posiadłości Brendana, czyli wspomnianego wcześniej Quivvy Church. Prace w studio trwały trzy miesiące, co wynikało z pewnej bardzo radykalnej decyzji. Otóż Brendan uznał, że do nagrania albumu nie potrzeba już będzie żadnych muzyków sesyjnych. Postanowiono rejestrować poszczególne utwory „ścieżka po ścieżce”, czyli nakładając na siebie kolejno nagrane instrumenty, sample i oczywiście wokale. Wszystkie instrumenty obsługiwali więc jedynie Brendan i Lisa, a znaczną część dźwięków stanowiła subtelna elektronika. Pomoc potrzebna była już tylko przy ostatecznym masteringu nagrań. Poproszono o to Milesa Showella, jednego z najbardziej uznawanych dźwiękowców specjalizującego się w obróbce dźwięku analogowego.

„Into The Labyrinth” ukazał się w Wielkiej Brytanii 13 września 1993, jednak premiera dotyczyła wyłącznie wersji na płycie winylowej. Zamieszczono na niej dodatkowo utwory „Bird” oraz „Spirit” znane z wydanej dwa lata wcześniej składanki „A Passage In Time”. Pod koniec roku wydano też wersję albumu na CD, którą pozbawiono tego dodatku.

Szósty longplay Dead Can Dance spotkał się z bardzo ciepłym przyjęciem krytyków, choć wśród starych fanów duetu opinie były raczej mieszane. Niektórzy mieli za złe wspomnianą różnorodność utworów, a co za tym idzie, zerwanie z ideą albumu koncepcyjnego. Wrażenie to potęgowało naprzemienne ułożenie na płycie utworów Brendana i Lisy, przez co muzyczny klimat zmieniał się jak w kalejdoskopie. Byli też tacy, którzy zarzucali - zwłaszcza utworom Perry'ego – odejście od wymagających muzycznych form na rzecz klasycznych, lekkich piosenek z klarownym podziałem na zwrotki i refren.
Odbiór w branży był jednak bardzo dobry, a album sprzedawał się znakomicie. Oto wyjątki z kilku recenzji:

Przez ponad godzinę trwania albumu przewija się zdumiewająca ilość dźwięków, które brzmią, jakby płynęły sprzed tysięcy lat. Istna mieszanina stylów. Być może jest to tym bardziej imponujące, że wszystko to zostało wykonane wyłącznie przez Perry'ego i Gerrard. To szczegółowy i soczysty album, a potencjalne hity pojawiają się niemal na każdej jego ścieżce. (all music)

Kto śledził poczynania duetu Gerrard – Perry od początku, bez trudu zauważał wyraźny zwrot w muzyce zespołu. Rozwijane od płyty „Spleen And Ideal” obszerne, dogłębne poszukiwania w obrębie europejskiej tradycji muzycznej, w tym muzyki epoki średniowiecza, która tak bardzo fascynowała Perry’ego, zostały tu zastąpione przez eksplorację muzyki świata. Wcześniejsze fascynacje zostały zsunięte na dalszy plan, choć nadal w niektórych kompozycjach wyraźnie się przebijają, a więc nadal ta europejska tradycja kulturalna odgrywa tu swoją rolę. Ale na pierwszym planie jest tutaj muzyka etniczna różnych części świata. Ciut temu albumowi brakuje do arcydzieł na miarę „Within The Realm Of A Dying Sun” czy „Aion”, ale jest to płyta bardzo udana. (art rock)

Prawda jest taka, że przyjęcie albumu nie obyło się bez krytyki. Dead Can Dance wchodzili w lata dziewięćdziesiąte cudownym "Aionem". Już on zapowiadał pewne rozluźnienie bardzo intensywnej atmosfery, jaka cechowała do tej pory muzyka Dead Can Dance. "Into the Labyrinth" tylko tę tendencję potwierdził; klimat kompozycji stał się lżejszy i przystępniejszy. Fala niezwykłej popularności muzyki etnicznej na początku tamtej dekady jedynie to wrażenie wzmocniła. Taka popularyzacja niezwykle wysokiej muzyki Dead Can Dance nie do końca spodobała się fanom, którzy do tej pory niemalże modlili się przy dźwiękach "Within the Realm of the Dying Sun", czy "The Serpent's Egg".
Myślę jednakże, że po latach sympatycy magicznego duetu zgodzą się ze mną, że była to krzywdząca opinia. "Into the Labyrinth" to cudowna płyta, wzbudzająca w słuchaczu tyleż zachwytu, co wzruszenia. To porcja muzyki skończonej - wypełniona wszelkimi emocjami, jakie mogą tylko nieść ludzkie dźwięki. (postindustry)

Ponieważ na początku lat dziewięćdziesiątych DCD stali się bardzo popularni na całym świecie, co potwierdziła udana trasa koncertowa po Stanach Zjednoczonych, wytwórnia 4AD podpisała kontrakt z Warner Bros Records na dystrybucję płyt grupy. Wsparcie takiego giganta znalazło odzwierciedlenie w liczbie ponad pół miliona sprzedanych egzemplarzy „Into The Labyrinth”, co jak na ten rodzaj muzyki jest dużym sukcesem.

Podobnie jednak jak w przypadku albumu „The Seprent's Egg”, który również początkowo nie spełnił oczekiwań dużej części fanów, po latach wiele utworów z „Into The Labyrinth” cieszy się dużym uznaniem, co wyraża się między innymi w bardzo pozytywnym ich odbiorze przez publiczność na koncertach. Brendan Perry powiada dziś natomiast, że jak do tej pory jest to w jego oczach najbardziej udany album Dead Can Dance.