Пробив брешь в бастионе «Би-Би-Эс», Фред Рус устремил свой взор на Копполу и здорово помог ему с актёрами. У него был талант находить типажи с удивительно точным попаданием актёра в персонаж. Применительно к «Крёстному отцу» он делал ставку на актёров итальянского происхождения из нью-йоркских театров с большим опытом работы на телевидении. Рус и Коппола решили задействовать в съёмках и непрофессиональных исполнителей. Главный критерий — соответствие образу героя, как, например, это вышло с бывшим борцом Лепни Монтана по кличке «Малыш-зебра», который только что вышел из нью-йоркской тюрьмы «Рикерс айленд» и сыграл в фильме роль Луко Брази. Звёздность имени па афишах для Копполы, как, впрочем, и для Олтмена, Богдановича и остальной молодёжи из обоймы «нового» Голиивуда, ровным счётом ничего не значила. «Я искал не звёзд, а людей, которые стали бы для меня настоящими американцами итальянского происхождения, но не за счёт коверкания языка «а-ля Луиджи», а просто потому, что они и есть итальянцы, говорящие с обычным нью-йоркским акцентом, — вспоминает этот этап работы над фильмом режиссёр.

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

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

Тем временем Коппола начал подыскивать места будущих съёмок. Он с удовольствием поедал пасту в доме родителей Скорсезе в «Маленькой Италии» Нью-Йорка. Рассказывает Марти: «Фрэнсис записывал говор моего отца на плёнку, чтобы лучше вслушаться в акцент. А мать постоянно давала ему советы по поводу актёров. Как-то за обедом она предложила кандидатуру Ричарда Конте и Фрэнсис согласился. В другой раз она спросила:

— Сколько дней ты собираешься снимать?

— 100 дней, — ответил режиссёр.

— Мало, этого недостаточно.

Тут мне пришлось вмешаться и сказать:

— Ма, хватит пугать Фрэнсиса».

Однако вопросы по актёрам оставались, что-то решалось, что-то нет. Например, кто будет играть Дона? Коппола считал, что эта роль принадлежит Марлону Брандо, но он был не в чести. О его похождениях во время съёмок «Мятежа на «Баупти» ходили легенды. Поговаривали, что он якобы «наградил» сифилисом половину женского населения Таити. У Брандо был очевидный перебор с весом, а, что ещё хуже, его последняя работа в фильме Джилло Понтекорво «Гори!» оказалась провальной.

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

Потрясённый увиденным, Джафф сдался. Коппола заранее снял на видеоплёнку момент работы Брандо над образом Дона Корлеоне: в огромных количествах он засовывал в рот бумажные салфетки, а на волосы наносил крем для обуви. «Я знал, что тратить время на Рудди и даже Эванса было бесполезно, потому что против Брандо был сам Бладорн. Именно поэтому я решил ехать в Нью-Йорк», — вспоминает режиссёр. Коппола установил в конференц-зале компании аппарат для воспроизведения видеоплёнки и, войдя в офис босса, спросил: «Можно господина Бладорна, на минуточку».

— Что ты тут делаешь, — спросил шеф компании Копполу, заглядывая в конференц-зал, одним глазом поглядывая на экран. — О, только не он, даже видеть не хочу этого сумасшедшего, — проревел Бландорн, увидев, как Брандо стал что-то делать со своими светлыми волосами. Он собрался, было, уже выйти, как заметил метаморфозу, которая начала происходить с кожей лица актёра — она вдруг стала съёживаться, словно надувной шарик, из которого спускали воздух. Бладорн чуть не поперхнулся:

— Кого это ты тут показываешь? Что это за старая свинья? По-тря-са-ю-ще!».