Herodot widział część tego gmachu i opisał go w swoim dziele. Oto co tam było powiedziane:

Jako znak jedności postanowili postawić po sobie pomnik, więc zbudowali labirynt, usytuowany opodal południowego brzegu jeziora Moeris, w sąsiedztwie miejsca zwanego Krkodilopolis (Miasto Krokodyli). Byłem tam i jest to coś nie do opisania. Gdyby przyjrzeć się wszystkim murom miejskim i budowlom publicznym w Grecji, widać że wszystkie one razem nie wymagały ani takich prac, ani tylu pieniędzy co ten labirynt. A świątynie w Efezie i Samos nie są przecież małe! To prawda, piramidy zapierają dech w piersiach i każda z nich dorównuje wielu budowlom grackim, ale nic nie może się równać z labiryntem.

Dalej w tym opisie czytamy:

Po pierwsze ma on tuzin wewnętrznych ogrodów, z których sześć uszeregowanych jest w części północnej. Wejścia do nich znajdują się naprzeciwko siebie. Mur zewnętrzny " bez otworów " otacza cały kompleks. Sam gmach ma dwa piętra i 3000 komnat, z których Gołowa znajduje się pod ziemią, a pozostałe 1500 powyżej.

Zwiedziłem i obejrzałem osobiście 1500 komnat naziemnych, tak że mówię o nich z własnego doświadczenia. Co do komnat podziemnych muszę opierać się na relacjach innych, bowiem Egipcjanie zabronili mi tam wejść. Mogły być tam groby królów, którzy byli twórcami labiryntu i grobi świętych krokodyli. Nie byłem tam, więc i wszystko, co o tym wiem, wiem z tego, co słyszałem. Komnaty górne pokazano mi. Trudno uwierzyć, że były dziełem rąk ludzkich. korytarze, łączące pokoje i kręte ścieżki pomiędzy podwórcami zapierały dech różnorodnością barw, kiedy przechodziłem pełen zachwytu z podwórców do komnat, z komnat do kolumnad, przez kolumnady do innych komnat i z nich wychodziłem na dalsze podwórce. Stropy były wszędzie wykonane z kamienia, a ściany pokryte reliefami przedstawiającymi postacie. Każdy podwórzec był otoczony szeregiem kolumn z jednolitych bloków białego marmuru.