As mentioned above, Ernest Borgnine was the producers' first choice to play Al Mansuh. Richard Widmark turned down the role of Rolfe four times before finally agreeing to do it on the condition that his good friend Sidney Poitier do the part of Al Mansuh. Producers initially objected before accepting. They also dodged a blackface bullet this way, since Al Mansuh is a Moorish ruler.
Director Jack Cardiff initially wanted Ursula Andress for the part of Gerda.
Robert Taylor was originally in the running for the part of Rolfe.