Впервые информация о том, что Данелия планирует снять мультфильм, основанный на его же двухсерийной киноленте 1986 года, появилась еще в 2005 году. В 2006 году был назван предварительный срок завершения работы над проектом - 2008 год.
В установленный срок мультфильм готов не был, однако Данелия сумел показать несколько эпизодов из него на фестивале в Ханты-Мансийске в феврале 2008 года.
Данелия заявляет, что «не хотел, чтобы анимационный фильм походил на игровой». Мультипликационная «Кин-дза-дза» создается в смешанной технике. В ленте будет присутствовать как двухмерная, так и трехмерная анимация. Также известно, что сам Данелия озвучил в мультфильме одну из ролей.