Originally, Fujin was meant to be the lead of the game (as a carryover from his and Raiden's endings in 4, where Raiden became an Elder God and Fujin became Earthrealm's protector god in his stead). Due to fan backlash, Raiden returned.
Sareena might have made it into the game, as her model was created during the end of the Deadly Alliance's development cycle (she was also intended to be playable in 4 and Deception). Instead, she was used in Tournament Edition (one of the two portable offshoots of DA for the GBA) and eventually was introduced into the console titles in Armageddon.
Mavado's first design◊ was more Spanish-influenced, but was deemed to be too goofy for the character and he was revamped into a more serious character.
Hsu Hao was originally named Kublai Khan (as in Genghis Khan; not to be confused with Shao Kahn). This can be seen his Mortal Kandies artwork from The Krypt and other concept art.
Stage Fatalities were considered. For example, the Lung Hai Temple stage would've had a Fatality involving the Great Sea Dragon of Outworld mentioned in the arena's bio.
Several pieces of concept art reveal characters and arenas that were unstable to be implemented into the game, such as the Water Temple arena. One of the more amusing and intriguing "what-ifs" was Zebron, a prince from another world clad in a tuxedo who resembled an anthropomorphic zebra.