Колыван, злодей одной из предыдущих частей серии, возвращается в Киев, чтобы открыть лавку по продаже китайских сувениров. Обознавшись, богатырский конь Юлий приводит его к князю Киевскому как иностранца и путешественника. Задумав осуществить переворот и привлечь на свою сторону бояр, Колыван в красках расписывает им западные традиции, но его замыслу мешает скорое прибытие богатырей.

Тогда Колыван устраивает сговор с Бабой Ягой: чтобы провернуть государственный переворот, они создают клоны богатырей, а оригиналы заточают в море и выбрасывают в океан. С помощью клонов Колыван выдает князя за сумасшедшего, а себя назначает регентом до поры его выздоровления. Баба Яга же, превратившись во фрейлину, присоединяется к его правлению.

Тем временем бочка с настоящими богатырями прибивается к берегу экзотического острова, населенного местными аборигенами. Смогут ли наши герои вернуться назад и в очередной раз спасти Русь до того, как Колыван установит на ней западные порядки.

Это полнометражный дебют режиссера анимации Владимира Феоктистова. Художник-живописец по специальности, когда-то Феоктистов пришел на «Мельницу» прорисовщиком. Пройдя там же, на студии, анимационные курсы, он вскоре стал помощником режиссера Владимира Торопчина, а потом поступил в Петербургский институт кино и телевидения и окончательно решил стать режиссером.

Когда продюсер мультфильма Сергей Сельянов приглашал на проект Елизавету Боярскую, он позвонил ей по телефону и сказал: “Лиза, я хочу вам предложить роль, о которой мечтает каждая актриса. Роль Бабы Яги”. Эта фраза покорила актрису, и она сразу согласилась, даже не поняв, что речь идет об озвучании мультфильма. Эта роль стала ее первой работой в области мультипликации. Позже Боярская отзывалась о своем персонаже как о “девушке с характером”.

Сергей Маковецкий во время озвучания первой части занимался записью реплик уже отрисованного персонажа князя Киевского, поэтому остался несколько недоволен недостатком свободы и простора для творчества. Но с каждым фильмом серии его герой приобретал все большую индивидуальность и все более длительное экранное время, что доставляло актеру огромное удовольствие. В итоге Маковецкий с ужасом думал о том, что в далеком 2004-ом году мог отказаться от предложения продюсеров. Он даже говорил, что озвучивать мультфильмы ему нравится больше, чем сниматься в кино.

В русских былинах Колыван не является ни богатым купцом, ни вообще отрицательным персонажем. Там он – один из богатырей, союзник Ильи Муромца и Самсона-богатыря. Впрочем, чаще всего он выступает в качестве эпизодического персонажа. А имя его происходит от старого русского названия города Таллина – Колывань.

На озвучании Колывана Федор Бондарчук сменил Андрея Толубеева. Ему понравилась идея создать образ отрицательного персонажа и тот факт, что оба они были лысыми. Кроме того, Бондарчука привлекла идея поработать на одной площадке с Сергеем Маковецким. По отзывам Бондарчука, их совместная деятельность доставляла ему “счастье неописуемое”. Бондарчук описывает Колывана как “злого, коварного, лысого, в общем – отвратительного мужика”.

Хотя по итогам проката и оценок критиков и зрителей мультфильм получил самые низкие показатели во всей серии, это не помешало ему собрать в мировом прокате 35 миллионов долларов при бюджете в 3.5 миллиона. Хотя сборы мультфильмов серии всегда были достаточно хороши, только с третьего фильма проекты начали покрывать свой производственный бюджет, а эта часть окупила его почти в десять раз.

Чтобы сделать тестовое озвучание персонажей мультфильма во время отрисовки, студия анимации «Мельница» привлекала Константина Бронзита. Культовая фигура современной отечественной мультипликации, Бронзит в одиночку наговаривал текст за каждого персонажа. Всего же над каждым мультфильмом трудилось 200-250 человек.