Идея снять фантастический фильм о другой планете пришла в голову режиссёру Георгию Данелии с подачи его друга — итальянского писателя и сценариста Торино Гуэрра. Тот пожаловался на русские морозы и посоветовал снять что-нибудь теплое: «У вас в России слишком холодные и длинные зимы — сделай сказку, чтобы можно было согреться!».
Данелия решил снять фильм про обитателей жаркой планеты, но в процессе обсуждения идеи со сценаристом Резо Габриадзе задумка полностью изменилась. Несколько месяцев они писали сценарий, а потом Данелия понёс его на утверждение в Госкино. Министр кинематографии честно сказал режиссёру: «Если бы это был не твой сценарий, я бы этот бред бросил читать на первой странице…» — но съёмки разрешили.

Фильм должен был назваться «Космическая пыль» — по эпизоду с участием продавца этой самой пыли, которого должен был играть Леонид Ярмольник. В ходе многочисленных переделок эпизод выпал из сценария вместе с Ярмольником и понадобилось новое название. Придумал его Евгений Леонов. В ожидании съёмок он от скуки напевал какую-то бессмыслицу: «У меня портфель-фель-фель, а в портфеле киндза-дза-дза-дза …» Всех это ужасно раздражало, а Георгий Данелия решил из этой белиберды сделать название фантастического фильма.

Помимо Леонида Ярмольника в фильме должны были сниматься, но не снялись ещё несколько актёров. Валентин Гафт был утвержден на роль пацака Би, но перед началом съёмок отказался от работы. Тогда режиссёр позвонил Юрию Яковлеву и предложил роль ему. Яковлев лежал в больнице, но фамилия Данелии произвела на него целительный эффект — он очень хотел с ним поработать, да ещё и в компании Станислава Любшина и Евгения Леонова, да в такой необычной роли! Через несколько дней Яковлев уже ехал на съёмочную площадку…
Одного из чатлан должен был играть Борислав Брондуков, но у актёра случился инсульт. Роль вычеркнули, но фамилия Брондукова осталась в титрах вместе с фотографией с проб. Всеми любимого ПЖ вместо не сумевшего освободить время для съёмок Ролана Быкова сыграл директор фильма Николай Гаро. Участие датчанина Норберта Кухинке запретили киночиновники, и в маленькой роли Абрадокса снялся сам Данелия.

«Скрипача» Гедевана играл сын сценариста — Леван Габриадзе. По сценарию его герой вез бутылку чачи, выпив которую инопланетяне пришли в восторг, продолжили застолье тормозной жидкостью из «пепелаца» и в результате вместо Земли попали на планету Альфа. Сцену уже отсняли, как началась антиалкогольная кампания — за чачу могли дать и 5 лет… Сцену пересняли — в бутылке появился уксус, а причиной попадания на Альфу стала техническая ошибка. Вышло не так смешно, но безопасно.

Съёмочной площадкой была выбрана пустыня Каракумы. Работу планировали начать ранней весной, пока не началась жара, но случилось непредвиденное… пропал «пепелац». Оказалось, что межзвездный космический корабль по ошибке уехал во Владивосток и вернётся только через месяц. «Пепелац» был увесистым — его сделали из обрезанной хвостовой части самолета, покрытой отфактуренным под ржавчину пенополиуретаном. К ней прикрутили винт, сделали дверь и поставили на колеса. Кстати, само название «пепелац» имеет грузинские корни. Это производная от грузинского «пепел» — бабочка.

Когда «пепелац» приехал-таки на съёмочную площадку, его решили ещё улучшить — немного обжечь горелкой. В результате пенополиуретан вспыхнул и с одного бока корабль прогорел… Пришлось срочно ставить заплатку. Неприятности вообще преследовали съёмочную команду — помимо многострадального «пепелаца» разнесло ураганом декорацию корабля в песках, в декорациях подземного «пепелаца» случился пожар, в «эцих» въехал пьяный водитель, а сделанная для фильма ракета взорвалась на старте… Оператор Павел Лебешев даже выдвинул теорию, что им мешают инопланетяне, которые не хотят, чтобы на земле о них узнали всю правду.

После премьеры к Георгию Данелии обратился американский режиссёр с предложением сделать спецэффекты для его фильма — очень уж его впечталил летающий «пепелац». Данелия сотрудничество не рассматривал, поэтому сказал, что это не спецэффекты, а настоящий летающий пепелац. Это разработки военных, и лучше обратиться к ним, так как скорее всего устройство пепелаца — военная тайна. Потом режиссёру позвонили из Министерства обороны и попросили больше не валять дурака… На самом деле в полет отправляли макет «пепелаца», который ездил по натянутой леске.

Съёмки начались летом, и работать было можно только рано утром или поздно вечером — весь день стояло невыносимое пекло. Режиссёр рассказывал, что на площадке все почему-то ссорились, хотя за кадром прекрасно общались. Он даже поругался с любимым актёром Евгением Леоновым, которого снимал уже двенадцать лет без единого конфликта! Потом местные рассказали, что с полудня до двух в этих местах вообще никто ничего не делает — происходят какие-то вредные для нервной системы излучения. Актёры вспоминали съёмки как трудные, но очень весёлые и дружные — всех спасало прекрасное чувство юмора и ироничное отношение к фильму. За исключением двух часов в день все друг в друге души не чаяли.

У Данелии была масса эскизов костюмов, но оказалось, что пошивочный цех киностудии занят работой над «Борисом Годуновым» Сергея Бондарчука. Понятно, что ради странного фильма про планету Плюк и пацаков никто портных не освободил. Тогда за дело взялась вся съёмочная группа: трикотажные майки и кальсоны обесцвечивали хлоркой, что-то подкрашивали чернилами, все дырявили, вытирали, прожигали… Данелия получил доступ на свалку военного аэродрома, откуда команда натаскала часть декораций. Удалось добыть и пару лётных костюмов — их разобрали на запчасти, сняв все сетки, пружинки, кольца и прочие мелкие штуки непонятного назначения, чтобы потом украсить ими «инопланетян».

Один из летных костюмов достался герою Юрия Яковлева, а вот наряд для персонажа Евгения Леонова собрали в прямом смысле с миру по нитке. К брезентовым матросским штанам Данелия приклеил найденную на свалке аэродрома блямбу непонятного назначения, сверху на Уэфа надели майку с пришитыми тесемками и вывернутую ворсом наружу фуфайку от водолазного костюма. Мягкие ботинки достались от фильма «Легенда о Тиле», а головным убором стал гульфик от лётного костюма… С остальными костюмами было проще — для девушки Цан просто взяли кусок ткани для тряпок, на чатланина Кырра надели найденное на помойке рваное пальто, а зимняя одежда для Гедевана и Машкова — это личный гардероб Георгия Данелии.

Киночиновники фильм «Кин-дза-дза!» пропустили без единой цензурной правки. Это всех удивило, так как это была не просто фантастика, но ещё и весьма небезобидная сатира. В прокате «Кин-дза-дза!» провалилась — зрители не понимали кого играют знаменитые и заслуженные актёры и что вообще происходит… Зато комедию с восторгом принимали на молодежных показах. Интересно, что «Кин-дза-дза!» стала набирать популярность с годами, и уже в 90-х у комедии было больше поклонников, чем на момент премьеры. В 2013 году был выпущен анимационный фильм «Ку! Кин-дза-дза», который стал последней режиссёрской работой Георгия Данелии.