И когда Аркадий Инин предложил Леониду Гайдаю сюжет для еще одной пародийной комедии «на злобу дня», тот с радостью ухватился за эту идею.

Появление сценария «На Дерибасовской хорошая погода, или На Брайтон-Бич опять идут дожди» было инспирировано из ряда вон выходящим событием, не забывшимся и по сей день: открытым и сознательным предательством последнего председателя КГБ Бакатина, который в 1991 году раскрыл американцам все схемы наших подслушивающих устройств в посольстве США в Москве. Этот постыдный факт Инин и его соавторы блистательно развили до полноценной сюжетной линии, красной нитью проходящей через последнюю комедию Гайдая. Сегодня эта линия может показаться абсурдной — подумать только, фильм рассказывает о совместной операции советской и американской спецслужб под лозунгом «КГБ и ЦРУ — дружба навек!». Но на тот момент подобный сюжет выглядел не менее правдоподобно, чем перспектива всеохватной кооперации во времена «Частного детектива».

Кстати, в самом начале работы над сценарием предполагалось, что это будет своеобразное продолжение «Операции «Кооперация» и, соответственно, главным героем останется Дима Пузырев в исполнении Дмитрия Харатьяна.

Но в итоге фантазия авторов породила совершенно иного протагониста — суперагента КГБ Федора Соколова: этакий «наш ответ Джеймсу Бонду». И на эту роль Гайдай поначалу планировал утвердить нового для себя молодого артиста — Александра Кузнецова, бывшего в то время такой же крупной звездой, как Харатьян. Но с Кузнецовым что-то не сложилось, и тогда Леонид Иович решился продолжить сотрудничество с полюбившимся ему Дмитрием. В конце концов Федор Соколов стал логичным продолжением Димы Пузырева, как в свое время культовый Шурик легко обернулся булгаковским инженером Тимофеевым.

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

О том, что в фильме могла бы сняться и действительно будущая звезда, неоднократно рассказывал в интервью Дмитрий Харатьян. По его словам, Гайдай после первых же проб остался настолько доволен Келли МакГрилл, что решил никого больше и не смотреть.

— Но сегодня будет еще одна девушка, — сообщили Гайдаю.

— Как зовут? — без интереса отозвался режиссер.

— Милла Йовович, — был ответ.

— Не надо, — поморщился Гайдай. — Двух Иовичей для одной картины будет многовато.

Так звездный час Миллы Йовович был отложен до 1997 года, когда ее снимет в «Пятом элементе» Люк Бессон.

Все остальные роли были отданы известным русским актерам, причем с некоторыми Гайдай никогда раньше не работал. Благодаря привычке снимать прежде всего ранее проверенных лицедеев Леонид Иович успел задействовать в своих фильмах далеко не всех артистов, которые ему нравились.

Будучи сам актером, Гайдай обожал представителей этой профессии — и как режиссер, и как зритель. По словам Нины Гребешковой, у него был огромный список действующих советских кинозвезд, которых он желал бы рано или поздно пригласить сниматься. Например, очень хотел поработать с Валентином Гафтом (так и не пришлось) — и нередко вздыхал перед очередными съемками: мол, опять не нашлось в сценарии подходящей роли для Гафта.

Судя по всему, нравился Гайдаю и другой «рязановский» артист — Андрей Мягков, как и прославившая его картина «Ирония судьбы, или С легким паром!».