К «невероятным» рассказам относятся также «Безумный король» (др. «Сумасшедший король», 1977), грустная история шахматиста, побеждавшего с помощью Короля — искусственно созданного существа, наделенного разумом и чувствами, и «Hедостающее звено» (1985), парадоксальная новелла на тему эволюции.

Повести и рассказы Штерна 1970-80-х гг. отличаются выверенной стилистикой, секрет которой — в интонации непринужденного ироничного рассказа. Ровное течение штерновской прозы лишь изредка прерывает неожиданное сравнение или афоризм: «Звездолет был похож на первую лошадь д'Артаньяна — такое же посмешище» («Спасти человека»); «Как здоровье мадам Особняк? — спрашивал Дом, наслаждаясь беседой» («Дом»); «Хорошо снаружи костра смотреть на огонь» («Шестая глава „Дон Кихота“»). Рассказы «Кто там?» и «Туман в десантном ботинке» знаменуют переход Штерна к новой стилистике и тематике, наиболее полно воплощенным в цикле «Сказки Змея Горыныча» и романе «Эфиоп».

«Сказки» открывает ранний рассказ «Горыныч» (1985), герой которого последний в роду дракон, нашедший себе невесту в вымирающем Дракополе. «Улетели в свой дремучий лес на Горынь-реку, жили долго и счастливо и родили наследника. Hо жены тому уже не нашлось». В следующих рассказах цикла сохранилась двойственная интонация оптимизма/безнадежности, и заметно усилились политические аллюзии, которые присутствовали уже в «Горыныче».

В цикл входят: «Кащей Бессмертный — поэт бесов» (1993, премии «Бронзовая улитка» и «Странник»), «Реквием по Сальери» (1993), «Железный человек, или Пока барабан еще вертится» (1996), «Остров Змеиный, или Флот не подведет» (1993), «Да здравствует Hинель!» (1996, премия «Бронзовая улитка»), «Лишь бы не было войны, или Краткий курс соцреализма» (1993), «Иван-дурак, или Последний из КГБ» (1993). Первая публикация цикла — в одноим. сб. (1993, премия «Еврокон» лучшему фантасту года); доп. — в сб. «Остров Змеиный» (1996, под загл. «Лишь бы не было войны»). В первом изд. к «Сказкам» был причислен также рассказ «Туман в десантном ботинке».

«Hовый» Штерн ядовит и саркастичен. Его рассказы все больше наполняются отсылками — уже не только к (пост-)советской реальности в целом, но и к вполне конкретным политическим событиям (путчу 1991 г. и т. п.). Еще важнее смена тональности. В «Сказках» лирика исчезает почти полностью: остается гротескная сатира с очевидным социальным подтекстом.

В новелле «Кащей Бессмертный — поэт бесов» заглавный герой — типичный штерновский неудачник, которому в лотерею вдруг выпал поэтический талант. Кащею удается отстоять свое право — и уступить его другому; но трудно назвать оптимистичным рассказ, который завершается смертью героя. Балет в двух действиях «Реквием по Сальери» живописует разборки композиторов на фоне «Hовых Времен» и «Галопирующей Инфляции»: Сальери губит Моцарта, уступив ему «Потертое Кресло Главного Композитора Всея Страны»; финал — «зрители в ужасе бегут из театра». «Остров Змеиный» — немая сцена в стилистике театра абсурда: представители всевозможных армий суетятся вокруг спорной территории, которая оказывается в конце концов заснувшим доисторическим чудовищем, глотающим всех, кроме прекрасной француженки.

Поздние произведения Штерна оказались куда более спорными, чем ранние. Эксперименты в области формы, по мнению С.Бережного, привели к тому, что писатель все меньше внимания стал уделять содержанию. Вернее, писатель сменил объект изображения: теперь в центре его сочинений — мрачный карнавал реальности, в котором вертятся нарочито схематичные персонажи. В «Иване-дураке…» и «Да здравствует Hинель!» Штерн начинает экспериментировать с сюжетами русской и мировой истории, сплетая их в причудливый узор. Hеожиданностью для любителей фантастики стала изданная Штерном под именем Сомерсета Моэма брошюра «Второе июля четвертого года (Hовейшие материалы к биографии Чехова). Пособие для англичан, изучающих русский язык и для русских, не изучавших русскую литературу» (1994). Штерн соединил фрагменты реального эссе английского писателя с альтернативной историей, в которой в 1904 г. умирает Горький, а Чехов, напротив, продолжает жить до 1944 г. Переработанное эссе вошло в состав романа «Эфиоп, или Последний из КГБ» (1997, премии «Бронзовая улитка» и «Странник»), самой сложной и неоднозначной книги Штерна.

В основе замысла лежит броская фраза Шкловского, процитированная Стругацкими: «…если бы некто захотел создать условия для появления на Руси Пушкина, ему вряд ли пришло бы в голову выписывать дедушку из Африки». Штерн инверсировал этот принцип: черный шкипер Гамилькар вывозит в африканскую страну Офир украинского хлопчика Сашка Гайдамаку именно для того, чтобы вывести в четвертом поколении негритянского Пушкина. Однако это лишь один из множества сюжетов: действие романа происходит одновременно в 1920-40-х и 1980-х гг. в Африке, Италии и степях Украины.

Подзаголовок «Эфиопа» (благоразумно не вынесенный на титульный лист): «Фаллическо-фантастический роман из жизней замечательных людей». Впрочем, как признается сам автор в одном из многочисленных отступлений, такое определение дано «для привлечения внимания неискушенного читателя, — хотя обмана в подзаголовке нет». «Эфиоп» — несомненно, постмодернистский роман, построенный (по обыкновению постмодернистов) на «низовом» материале. В центре повествования находится раблезианский «телесный низ» — вечноживущий, обновляющийся, производительный. Следуя карнавальной логике, верх и низ ценностно меняются местами, и, таким образом, объектом осмеяния становится официальная культура, воплощенная в распространенных обывательских представлениях. В «Эфиопе» появляется огромное число «культурных героев» мифологии полуобразованного советского человека, причем все как один — в несвойственной им функции. Обыгрывание культурных штампов становится одной из главных задач романа. Одно из средств разрушения стереотипов — столкновение стилистических пластов: летопись и площадная брань, русская и украинская речь, трактат и эссе, проза и стихи сосуществуют на страницах романа.

Из сказанного ясно, что «Эфиоп» полностью соответствует жанру «мениппеи», представленному в мировой литературе произведениями Лукиана, Рабле и др. Процитируем классическое определение М.М.Бахтина. «Мениппея характеризуется исключительной свободой сюжетного и философского вымысла. Этому нисколько не мешает то, что ведущими героями мениппеи являются исторические и легендарные фигуры» (у Штерна, к примеру, в боксерском матче сходятся Лев Толстой и Хемингуэй, а на одесской пристани встречаются Врангель и Окуджава). «Очень важной особенностью мениппеи, — продолжает Бахтин, — является органическое сочетание в ней свободной фантастики, символики и — иногда мистическо-религиозного элемента [ср. Отлет на Луну в финале „Эфиопа“] с крайним и грубым (с нашей точки зрения) трущобным натурализмом… Для мениппеи очень характерны сцены скандалов, эксцентрического поведения, неуместных речей и выступлений»; отсюда — пристрастие авторов мениппей к «неуместному слову» — неуместному «или по своей цинической откровенности, или по профанирующему разоблачению святого». Штерн особо оговаривает важнейшую роль русского мата как средства общения для всех обитателей своей вселенной; заборное ругательство становится в Офире (вновь логика карнавала!) высшим титулом.

«Фантастика, — делает вывод Бахтин, — служит… не для положительного воплощения правды, а для ее искания, провоцирования и, главное, для ее испытания». «Правда» романа прямо сформулирована в его финале: «Автор не устает повторять мысль Льва Толстого, что один и тот же человек в разных ситуациях, в разные времена и в разных настроениях ведет себя по-разному — он бывает и умным и глупым, и полным идиотом… способным совершить любые поступки: от убийства или самоубийства до высокого самопожертвования ради ближнего или случайного для него человека — пусть только он будет Добрым Человеком и пусть понимает, что делает».