V Kmotrovi se místo Branda a Pacina málem objevila úplně jiná jména. Coppola musel vyjednávat
„Boj ohledně obsazení rodiny Corleoneových byl nelítostnější než válka, které se postavy účastní na plátně,“ vzpomínal ve svých pamětech The Kid Stays in the Picture producent Robert Evans. I s ním jakožto zástupcem studia Paramount vedl Coppola sáhodlouhé a vyhrocené diskuze, když licitoval téměř o každém jménu v obsazení.
Problémy začaly hned u hlavní role Vita Corleoneho. Coppola si vysnil slavného a opěvovaného Marlona Branda, což se studiu z logických důvodů nelíbilo. Brando měl renomé potížisty a excentrika, s nímž se těžko pracuje, navíc se během 60. let nevyhnul několika kasovním propadákům. Zástupci Paramountu po prvotním odmítání nakonec Branda Coppolovi schválili, ale jen za poměrně přísných podmínek.
Herec se tak stal částečně odpovědným za případné navyšování rozpočtu kvůli jeho chování, obdržel na hlavní hvězdu relativně malý plat (čtvrt milionu dolarů plus procenta z tržeb, na nichž se následně finančně zahojil) a musel se účastnit kamerových zkoušek. Brando si podle Coppoly v jednu chvíli usmyslel, že postava Vita byla někdy v minulosti postřelena do krku, a tak musí mluvit zvláštně. Natočené zkušební záběry se však zástupcům studia velmi líbily, a tak rozporuplného Branda nakonec upřednostnili před svými původně preferovanými jmény jako Orson Welles, Ernest Borgnine, Charles Bronson či Anthony Quinn.
Následně se Coppolovi podařilo domluvit do vedlejších rolí Roberta Duvalla (rodinný právník a consigliere Tom Hagen), Diane Keaton (Michaelova přítelkyně Kay Adams) či Johna Cazaleho (Michaelův bratr Fredo). Navzdory blížícímu se začátku natáčení se však stále nepodařilo obsadit druhou nejdůležitější roli, Michaela Corleoneho, jehož osobnostní proměna je jádrem celé kmotrovské trilogie.
Coppola chtěl pro roli dosud neznámého Ala Pacina, který ale tou dobou měl na kontě divadelní cenu Tony. Mladý, filmově nezkušený a navíc pouze 168 centimetrů měřící herec se Evansovi a dalším studiovým pohlavárům nepřekvapivě nezamlouval. Producenti si v roli představovali etablovanější jméno typu Jacka Nicholsona, Warrena Beattyho, Roberta Redforda, Ryana O’Neala, Dustina Hoffmana, Martina Sheena či Burta Reynoldse. Z castingového procesu organizovaného studiem ale nakonec nejlépe vyšel James Caan.
Coppola se s tím však nesmířil a nadále loboval za Pacina. Evans tedy přišel s řešením: Michaela může hrát Pacino za předpokladu, pokud Caan dostane aspoň roli jeho bratra Sonnyho. Na to Coppola zareagoval prásknutím dveřmi, jelikož do úlohy Sonnyho už byl domluvený Carmine Caridi. Výškový rozdíl mezi Pacinem a 193 centimetrů měřícím Caridim by však podle Evanse na plátně nepůsobil vůbec dobře. Po deseti minutách rozmýšlení se tedy Coppola za Evansem vrátil a nabídku odkýval. Studio ještě muselo Pacina vyvázat z malé roli v krimikomedii Banda, která neuměla pořádně střílet (kde nakonec Pacina nahradil Robert De Niro, neúspěšně se ucházející o větší role v Kmotrovi) a Caridimu nezbylo než se spokojit s menší rolí v pokračováních Kmotra.
Vztah mezi Francisem Fordem Coppolou a studiem Paramount byl tedy od začátku poměrně napjatý, nakonec se však díky Kmotrovi dočkaly obrovského úspěchu obě strany. A ačkoli je Brandovo ztvárnění Vita Corleoneho bez přehánění ikonické a Michaelova proměna díky použití tehdy ještě neznámého Pacina uvěřitelnější, přesto může být lákavé si představit alternativní vesmír, v němž se hlavních rolí ujali třeba Orson Welles a Robert Redford.