При выборе актеров самая большая проблема возникла с исполнителем главной роли - Остапа Бендера. Весь январь и практически весь февраль Гайдай и его ассистенты безуспешно пытались найти актера, который сумел бы воплотить на экране этого героя. Гайдаю был необходим актер, который оказался бы полной антитезой Сергею Юрскому, сыгравшему великого комбинатора в фильме "Золотой теленок". В этих поисках Гайдай пересмотрел чуть ли не всех советских звезд мужского пола, кто по своему возрасту, внешним данным и таланту подходил на эту роль. Были просмотрены 22 кандидата. Чтобы читателю было ясно, каким тщательным был отбор, назову некоторых из этих актеров: Андрей Миронов, Алексей Баталов, Михаил Козаков, Владимир Высоцкий, Анатолий Кузнецов, Олег Борисов, Спартак Мишулин, Никита Михалков, Александр Белявский, Владимир Басов, Фрунзик Мкртчян, Николай Губенко, Евгений Евстигнеев, Александр Лазарев, Валентин Гафт и др. Однако на первоначальном этапе никто из них не удовлетворил ни Гайдая, ни членов худсовета. Видимо, тогда в порыве отчаяния Гайдай предложил попробоваться на роль певцу Муслиму Магомаеву. Но тот отказался, поскольку, во-первых, прекрасно знал свои возможности, а во-вторых - не любил бессмертное творение двух великих сатириков.
Не менее драматично шли поиски стульев для фильма. Их нужно было раздобыть не двадцать четыре (два гарнитура), а в два раза больше, чтобы в процессе съемок можно было корежить их без опаски остаться без реквизита. Поначалу надеялись отыскать их с помощью рядовых советских граждан. Для этого 1 ноября 1969 года в газете "Вечерняя Москва" поместили объявление, в котором киношники просили москвичей продать имеющиеся у них стулья работы мастера Гамбса. Однако вскоре выяснилось, что таких стульев в городе практически не осталось. Только случайно, через третьи руки, удалось узнать, что где-то на Арбате живет старушка, у которой чудом сохранился один-единственный (!) стул Гамбса: из орехового дерева, обитый английским ситцем. Киношники бросились туда. Нашли эту бабульку и действительно обнаружили у нее искомый стул. Но на все уговоры продать его, старушка отвечала категорическим отказом: дескать, он дорог ей как память. Тогда упросили ее разрешить сфотографировать стул, чтобы потом по этому снимку попытаться сделать рисунки, по которым опытные мастера смогли бы воспроизвести нужное количество стульев. Но это был еще не конец истории.
Как выяснилось, в Советском Союзе мастеров, умеющих делать гамбсовские стулья, не осталось. Единственное место, где такие умельцы были, - это Объединенная Арабская Республика (эта страна славилась тем, что была первой в мире по изготовлению мебели "под старину"). Направили туда запрос, и вскоре получили ответ: если заплатите валютой, то сделаем хоть тысячу нужных стульев. Пришлось платить. Через несколько месяцев - в феврале 1970 года - партия стульев "под Гамбса" в количестве 40 штук прибыла в Москву.
Кстати, многие другие старые вещи, которые мы теперь видим в фильме, были найдены в пределах Союза. Например, у москвичей купили: граммофон (его принес житель с Башиловской улицы), карту Москвы 1926 года, которую Бендер и Киса рассматривают в общежитии (продала гражданка М. Каверина), потертый коричневый саквояж (его будет носить Киса), коробки из-под печенья "Тов. Эйнемъ" и "Северная смесь", старые журналы и др.
А теперь вновь вернемся к поискам актера на роль Остапа Бендера. Поскольку время поджимало, а главного исполнителя все не было, Гайдай решил пойти самым простым путем: он предложил эту роль актеру, который из числа "22-х" выглядел наиболее выигрышно - Владимиру Высоцкому. Тот, не избалованный чрезмерным вниманием к своей персоне киношных режиссеров (за 10 лет сыграл в кино всего лишь две главные роли, причем, один фильм "Интервенция" - до зрителей при его жизни так и не дошел), согласился. Но в начале марта, когда пришло время сниматься, Высоцкий внезапно сорвался в очередное "пике" - то есть попросту запил. И Гайдаю пришлось срочно искать ему замену, причем опять из того же списка "22-х". Новым кандидатом на роль Бендера стал Александр Белявский. Именно с ним 10 марта 1970 года начались съемки фильма в 6-м павильоне "Мосфильма". Однако начались они неудачно. Почему? Перед началом работы, по давно заведенному обычаю, Гайдай должен был разбить бутылку шампанского. Так сказать, на удачу. Но она не разбилась. По всем приметам это был плохой знак. Гайдай очень сильно расстроился и на все заверения своих коллег, что все обойдется, ответил: "Нет, я чувствую, что это неспроста. Мы еще хлебнем горя на съемках". Как в воду глядел.