It stars Charlton Heston as British General Charles "Chinese" Gordon and Laurence Olivier as Muhammad Ahmed (a Sudanese leader whose devotees proclaimed him the Mahdi), with a supporting cast that includes Richard Johnson and Ralph Richardson.

[7] The film had its Royal World Premiere at the Casino Cinerama Theatre, in the West End of London, on 9 June 1966, in the presence of Princess Margaret and the Earl of Snowdon.

Commanding the force is former Bombay Army soldier Colonel William "Billy" Hicks (Edward Underdown), now a private individual paid by the Egyptian government.

He is defeated by native tribesmen led by Muhammad Ahmed (Laurence Olivier), a Nubian religious leader of the Samaniyya order who has declared himself Mahdi.

He could send colonial military hero Major General Charles George Gordon (Charlton Heston) who has strong ties to Sudan, having tried to break the slave trade there, but Gladstone distrusts him.

He gains the Mahdi's respect and, in the verbal fencing at the parley, discovers that the Sudanese leader intends to make an example of Khartoum by taking the city and killing all its inhabitants.

In the end, Gordon's head is cut off, stuck on top of a long pole, and paraded about the city in triumph, contrary to the Mahdi's injunctions.

In the United Kingdom, public pressure, and anger at the fate of Gordon, eventually forces the British and their Egyptian allies to re-invade the Sudan ten years later, and they recaptured and colonised Khartoum in 1898.

The colorful Julian Blaustein production builds in spectacular display, enhanced by Cinerama presentation, while Charlton Heston and Laurence Olivier propel toward inevitable tragedy, the drama of two sincere opponents.

"[28] Clifford Terry of the Chicago Tribune unfavorably compared the film to Lawrence of Arabia, writing "Khartoum is nothing more than a routine desert drama, full of sand and fury, signifying very little."

He blamed Dearden and Ardey, criticizing his script for failing "to grasp that however complex an individual, he nevertheless has a core, and covers up the character shallowness and story inconsistencies with grandiose gab.

[31] Patrick Gibbs of The Daily Telegraph criticized the film for its historical inaccuracies and felt neither Olivier or Heston convey "the personal magnetism attributed" to their characters.

[34] In the 21st century, historian Alex von Tunzelmann criticized the film for "factual inaccuracies" and Olivier's "unrealistic accent" and blackface makeup.

[35] Literature professor Edward Said criticized Khartoum for what he described as a pro-colonial propagandistic portrayal of good versus evil by clashing "despotically violent Arab masculinity against a noble, rational Western one.

"[36] Conversely, editor Dennis Schwartz described the film as "a visually stunning historical epic, smartly acted and lavishly produced, that gives one a good look at that period’s political intrigues but does little to tell us about the two religious zealots–Gordon and the Mahdi.

"[37] In a 1978 article for Film Comment, Martin Scorsese wrote Khartoum was one of his guilty pleasures: "Charlton Heston... is marvelous; and Laurence Olivier has a lot of fun as the Mahdi, with a space between his front teeth.