Работа над музыкальной сказкой "Алиса в стране чудес" началась в 1973 году и продолжалась с перерывами более двух лет. Процесс столкнулся с множеством препятствий, всё шло крайне медленно. Евгении Лозинской, ответственному редактору фирмы "Мелодия", понадобилось больше года, чтобы добиться разрешения на запись этой сказки - устного разрешения, письменного ей так и не дали. Кроме бюрократических проблем, были и творческие. Высоцкий, несмотря на важность для него этого редчайшего шанса появиться в качестве автора на пластинке, долго отказывался от участия в программе, ссылаясь на непонимание того, как это всё должно звучать. Тем не менее в конце концов его удалось убедить. В поисках нужного звучания Владимир Высоцкий создал для этой сказки 27 песен, но в итоге сам спел только три. Музыку написал Евгений Геворгян, он же и аранжировал песни Высоцкого.
Сейчас эта сказка выглядит вполне безобидно, но после её выхода на пластинке в 1976 году она мгновенно приобрела статус "кукиша в кармане". Сыграли свою роль и участие культового поэта-барда, и тонкие двусмысленности текста, которые тренированное ухо советского человека легко отфильтровывало от невинной сказочной канвы. Пластинку раскупали, ею "угощали" гостей, её "антисоветскость" разносили в преувеличенном виде слухи.
Практически сразу после записи пластинки состоялась коллегия Министерства культуры, на которой Наталья Сац - основатель и руководитель целой плеяды детских театров и виднейщий детский театральный авторитет в СССР - подвергла "Алису" жесткой критике, прежде всего за песни Высоцкого, которые она назвала "чудовищными". Мюзикл спасла от полного разгрома Белла Ахмадулина: с ней, уезжавшей в Париж, буквально перед вылетом самолёта успел переговорить Высоцкий. Белла Ахмадулина выступила с новогодним поздравлением, опубликованном в "Литературной газете" - она похвалила мюзикл, она похвалила фирму "Мелодия"... В итоге критики поутихли и пластинка не "легла на полку", а продолжила свой путь к слушателю.