Колоритной парой стал дуэт перманентно пьяного бузотера Степана (Вячеслав Невинный) и тишайшего еврея со скрипкой Соломона (Роман Карцев), вечно становящегося жертвой внезапных приступов антисемитизма, которым подвержен его друг.

«Обычно, когда актеру хотят дать роль в кино, звонят ассистенты режиссера, — рассказывал Карцев. — А Рязанов мне сам позвонил: „Вот, Роман, я вас приглашаю“. Разница! Речь шла о „Небесах обетованных“. И я был ошарашен таким вниманием к эстрадному артисту. Ответил, что согласен, не читая сценария, хотя всегда все сценарии читаю. Просто Эльдару Александровичу доверяю полностью. Так мы и познакомились — по телефону. <…>

Снимался я у Рязанова в фильмах „Небеса обетованные“, „Предсказание“ и „Старые клячи“. Для меня кино — хобби, а не самоцель, мне там все интересно: как свет ставят, про что на площадке разговаривают. А вот Рязанов на съемках занимается только делом. Ничего постороннего, никаких побасенок, анекдотов — все подчинено работе. Мне нравится, что актер для него соавтор, что можно импровизировать. Я в „Небесах обетованных“ придумал крылатую фразу. Там есть эпизод, когда Вячеслав Невинный — он антисемита играл — выгоняет меня из моей каморки и кричит: „Еврейская морда!“ А я ему в ответ: „Вот так всегда. Чуть что, кричат: ‘Бей жидов, спасай Россию!’ Жидов перебили, а Россию так и не спасли“. И Рязанов эту фразу взял и вставил в сценарий.

На съемках меня страшно удивило, что Эльдар Александрович с утра ничего не ел. А ведь весь день на свежем воздухе! Подносили ему только кофе и какие-то бутербродики. И мы с женой пригласили его к нам домой: пусть съест все, что сможет, пусть попробует настоящую одесскую пищу — фаршированную рыбу, консервированный арбуз, холодец… Потом и мы были у него в гостях, я даже в бильярд поиграл. Рязанов — очень домашний. И есть в нем что-то такое, что помогает человеку раскрыться. Он молчит, присматривается к тебе, каким-то образом незаметно нажимает на твои „болевые точки“ — и ты начинаешь говорить. Если ему нравится компания, он входит в беседу и чувствует себя прекрасно, если ему скучно, может сказать, что хочет спать, и уйдет. Но по-человечески с ним всегда хорошо — и это важно».

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