В центре Москвы, несмотря на холодную погоду, стоял босоногий человек в порванном пальто и задавал прохожим странный вопрос: «Скажите номер вашей планеты в Тентуре или хотя бы номер Галактики в Спирали? Я перепутал контакты и теперь не могу вернуться домой». Случайные прохожие, которыми оказались прораб Владимир Николаевич Машков («дядя Вова») и грузинский студент Гедеван  Александрович («Скрипач»), приняв его за сумасшедшего и, пытаясь убедить его в том, что он болен, нажали какой-то контакт на «машинке перемещения» (”да можно…”), которую он им показывал. Сразу после этого дядя Вова и Скрипач очутились на жаркой пустынной планете Плюк в галактике Кин-дза-дза.

Жители этой планеты выглядели как люди и быстро освоили русский язык, так как умели читать мысли, однако их собственный язык состоял лишь из нескольких слов. Хотя планета Плюк оказалась технически более развита, чем Земля (доступны путешествия в космосе, межпланетная связь, более совершенное оружие и т. п.), техника её обитателей была ржавой, изношенной и плохо работающей.

Общественное устройство планеты оказалось расистским. Всё население Плюка, как и других планет Галактики Кин-дза-дза (например, Хануда), делилось на две категории - «чатлане» и «пацаки», принадлежность к одной из которых выяснялась с помощью визатора. Плюк был чатланской планетой, поэтому пацаки на Плюке должны были носить в носу колокольчик (цак) и при встрече с чатланином приседать перед ним особым образом (”делать Ку“). Существовали и другие виды дискриминации пацаков - например, им назначались более жесткие наказания за правонарушения, артисты-пацаки имели право выступать только сидя в железной клетке, существовала сегрегация в общественном транспорте и др.

Дядя Вова и Скрипач, оказавшиеся пацаками, ищут способ вернуться на Землю. Они вступают в контакт с двумя артистами — пацаком Би и чатланином Уэфом, у которых есть собственный космический корабль — пепелац. Однако для межзвёздных полетов пепелацу требуется особая деталь — гравицаппа, отсутствующая в пепелаце Би и Уэфа (похищенная у них во время гастролей на Плюке). Таким образом, чтобы вернуться домой, землянам приходится заняться поисками гравицаппы, а затем и спасением своих новых друзей из лап местных блюстителей закона — эцилоппов. Неожиданным подспорьем оказывается то, что величайшей ценностью на Плюке являются спички, которые здесь называют «КЦ», и обладание которыми повышает социальный статус. К сожалению, из-за неприспособленности землян к реалиям жизни на Плюке весь запас спичек Владимира Николаевича оказывается потерянным для землян (частично, похищен при неудачной попытке приобрести гравицаппу за контрабандный КЦ, частично присвоен эцилопом в качестве взятки за смягчение наказания Уэфу и Би, частично испорчен самим Владимиром Николаевичем при машинальных попытках закурить в стрессовых ситуациях).

К счастью для себя земляне открывают новый источник дохода - земные песни в их исполнении находят горячий отклик в душах плюкан. Хорошие заработки позволяют надеяться на скорейший выкуп Уэфа и Би из плюканской тюрьмы (”эциха”). К сожалению, после освобождения артистов из эциха (происшедшего однако не путем выкупа, а путем учинения небольшого бунта против главы местной власти - Господина ПЖ) выясняется, что возврат на Землю при помощи пепелаца крайне затруднителен, потому что на пути между Плюком и Землей находится планета Альфа.

Жители Альфы — высокоразвитое общество, стремящееся исправить все недостатки Вселенной и навязать всем своё понимание мира. Они имеют привычку превращать оказавшихся в их распоряжении плюкан и хануидян в кактусы, так как считают продолжение жизни в виде растения благом для них (и для всех). Би и Уэф предлагают землянам не лететь на Землю, а остаться с ними, выкупить опустошенную войной с Плюком пацакскую планету Хануд и воздух к ней, после чего установить собственное деспотичное правление над всеми, кто решит переселиться на Хануд. Но в итоге дружба берёт свое, и артисты, рискуя собой, пытаются провезти Гедевана и Дядю Вову на Землю мимо планеты Альфа. В результате этой попытки Би и Уэф оказываются во власти жителей Альфы, которые по своему обыкновению собираются превратить их в кактусы. Но, по просьбе землян, высказанной от имени планеты Земля, возвращают всех четверых на Плюк, в прошлое, где Уэф и Би еще сидят в эцихе. Там землян находит босоногий странник по косвенной вине которого те оказались на Плюке. Странник возвращает землян на Землю, а Уэф и Би отказываются перемещаться вместе с ними, так как не представляют себе жизни в обществе, где отсутствует цветовая дифференциация штанов. Однако, имея в распоряжении гравицаппу и транклюкатор, они могут надеяться на повторный побег из эциха.

После возвращения на Землю, все произошедшее дяде Вове и Гедевану кажется странным сном, пока они случайно не встречаются друг с другом на том же самом месте в Москве, где они повстречали странника в начале фильма…