КЭС отослал рассказ в Weird Tales, где Фарнсуорт Райт отверг его как «слишком поэтичный и красиво написанный»; затем рассказ отвергли в журнале Argosy. В октябре 1932 года КЭС переписал текст и, на некоторое время оставив надежду его продать, включил в свой сборник «Двойная тень и другие фантазии»; еще позднее он предлагал сокращенный и отредактированный вариант в Esquire, где редактор Арнольд Гингрич отверг текст, поскольку тот «напоминал одновременно [Эдгара Райса] Берроуза и [Джеймса Брэнча] Кейбелла», что возмутило и озадачило КЭС до крайности. В итоге эта сокращенная и отредактированная версия вышла в октябре 1938 года в Weird Tales.
На протяжении своей предпечатной истории рассказ несколько раз менял название и последовательно побывал «Лабиринтом Мул-Двеба» («The Maze of Mool Dweb»), «Чародейским лабиринтом» («The Enchanter’s Maze»), «Лабиринтом чародея» («The Maze of the Enchanter») и «Лабиринтом Маал-Двеба» («The Maze of Maal Dweb»); это последнее название КЭС в итоге предпочел оставить за сокращенной опубликованной версией, а редакторы The Collected Fantasies of Clark Ashton Smith выбрали другое, чтобы отличать полную версию, которую они опубликовали и которая переведена здесь.
В 1935 году Уильям Уиттингем Лайман-мл. (1885–1983), корреспондент КЭС и преподаватель Лос-Анджелесского неполного колледжа, включил «Лабиринт Маал-Двеба» и четыре стихотворения КЭС в учебник «Литература сегодня» («Today’s Literature»), который составил вместе с двумя коллегами; рассказ сопровождался вопросами по теме («Ожидали ли вы счастливого финала? Конец вас удивил?»).
…опасный хитроумный лабиринт… коварные ловушки и чудовищные напасти, изобретенные жестоким Дедалом. – Дедал, персонаж древнегреческих мифов, – блестящий и амбициозный инженер и изобретатель; помимо многих других своих достижений, построил на Крите Кносский лабиринт, в котором обитал Минотавр.