Originally, Capcom Fighting All-Stars was planned to be a 2D sequel to Capcom vs. SNK 2: Mark of the Millennium 2001, before being converted to 3D. However, due to SNK's financial troubles and restructuring, the title was redesigned as a Capcom-only crossover with twenty former SNK members designing it, using the models previously built for the original title. Like SNK's KOF: Maximum Impact games, it was designed to translate a 2D fighting game series into 3D. This was done previously in the Street Fighter EX series, which Capcom co-produced with Arika. Capcom beta-tested the game, but after negative feedback from players and more months in development, the game was canceled in August 2003. According to an interview with former The King of Fighters director Toyohisa Tanabe, a secret character from Tanabe's old company (SNK) was set to be playable in Capcom Fighting All Stars.. While not confirmed, the figure bears a heavy resemblance to K' or Kyo Kusanagi.

The shadow of fear was approaching Metro City. A man only known as Death, was running around Metro City with a bomb. The bomb was codenamed "Laughter Sun". Mayor Mike Haggar contacted the characters listed above in order to locate and defeat Death and then defuse the bomb. Codes were needed to disarm the bomb, and that is where the Code Holders subtitle of the game comes into play. D. D. and his teammates, Rook and Ingrid, were the Code Holders. Their codes are Ogre, Fallen Angel, and Isis. The game had a time limit, and depending of how long the player took to finish the game, the ending would vary.