Choć to właśnie w Polsce udało się dofinansować produkcję Labiryntu – i to pomimo słabo zakamuflowanej krytyki totalitaryzmów – cenzorzy na kolaudacji mieli wątpliwości, czy film nadaje się do puszczenia w obieg. W jednej scenie cenzura dopatrzyła się wizerunku przywódcy Związku Socjalistycznych Republik Radzieckich, Nikity Chruszczowa, na co Lenica odpowiedział, że to tak naprawdę władca Austro-Węgier, Franciszek Józef I – co było zresztą prawdą. Ze względu na wieloznaczność symboliki filmu Labirynt został dopuszczony do rozpowszechniania, ale był początkowo dystrybuowany w ograniczonym obiegu, głównie festiwalowym. Dopiero po wielkim sukcesie festiwalowym pokazano go w polskich kinach i telewizji (w audycji Kino krótkich filmów po godzinie 23).
Odbiór Andrzej Kossakowski w retrospektywnym rozdziale Historii filmu polskiego uznał Labirynt za jedno z „najznakomitszych zjawisk w animacji światowej”, cechujące się klarowną kompozycją formalną: „nie ma tu ani jednego elementu, który nie pasowałby do całości, brak choćby jednej klatki nakręconej ponad potrzebę”.