The story of the video game states that Mathayus has just finished his assassin training and is given his first assignment by the Akkadian king, Urmhet. Of course, this doesn't jive with the depiction of Mathayus' youth in Rise of a Warrior, produced later, but having more weight of canon by virtue of being a movie (though a direct-to-video one). In Rise of a Warrior, Mathayus completes his training while the Akkadian Empire is under the kingship of Sargon, not Urmhet. Here, Mathayus is also depicted as older at the completion of his training (represented by The Rock's likeness here rather than Michael Copon's as in Rise of a Warrior). For purposes of continuity, we must take the story-points of Rise of a Warrior as the canonical ones when there is a conflict with the video game story. Since Mathayus is seen as older here, we can assume that this mission is just the latest he's undertaken (not the first) and that Urmhet has since become king of the Akkadian Empire, after first Sargon, killed by Mathayus, and Shalmaneser who succeeds Sargon, both seen in Rise of a Warrior.

Mathayus travels to Kehmet to deal with the warlord he's been hired to assassinate. As far as I can tell, Kehmet is a fictional city.

In Kehmet, Mathayus is forced to deal with Anubis himself. Anubis was the jackal-headed god of the afterlife and mummification in ancient Egypt. Mathayus will later, in the prologue of The Mummy Returns, make an unholy pact with Anubis to be given victory over Thebes.

A sorcerer called Magus tempts Mathayus with a place at his side. The word "magus" itself is Latin for "magician" or "sorcerer"; of course, the term originated much later (17th Century) than the time period of the Akkadian Empire (c. 3000 BC).

Returning to the Akkadian kingdom, Mathayus is attacked by humanoid falcons, Horus warriors. In ancient Egypt, Horus was one of the chief gods and was depicted as having a falcon's head.

During the course of the story, Mathayus sails to the island of Crete to seek the mystical Sword of Osiris to kill Magus and there faces off against the Minotaur, just as he had sailed to Crete to seek the Sword of Damocles to kill Sargon in Rise of a Warrior! (Mathayus must have had a sense of déjà vu through this particular part of the adventure!) The Sword of Osiris appears to be a fictional weapon, though it is said within the game to be the sword used by Set to kill his brother Osiris. In ancient Egyptian mythology, the god Set killed his brother, Osiris, and cut the body into pieces, in their feud over rulership of Egypt. The Sword of Osiris will appear again in the story of the later Scorpion King video game The Sword of Osiris.

On Crete, Mathayus also faces and kills one of the Gorgons. The Gorgons were three hideous sisters of Greek mythology with hair made up of venomous snakes and whose visage could turn the viewer to stone.

Also on Crete, Mathayus journeys to the Netherworld and meets up with the Sphinx. The Netherworld, of course, is a term used for the underground realm of the dead in many religions. A sphinx is a mythical creature that is half feline and half human, seen in the mythologies of many different cultures throughout the world.

In retrieving the pieces of the Sword of Osiris, Mathayus defeats Bast and Apep. Bast was a goddess of ancient Egyptian mythology, the goddess of cats, Lower Egypt (northern Egypt), the sun, and the moon. Apep is the evil serpent god of darkness and chaos in Egyptian mythology who later became known as Set himself (of course, as stated earlier, within the mythology of this game, the Sword of Osiris was said to have already been used, by Set, to kill Osiris, not to mention that Set himself appears for the climactic battle of the game, so this may not be the same Apep).

Mathayus next journeys to the Tower of Babel, known in the real world mostly for its part in the story of the Book of Genesis in the Old Testament of The Bible. Most Biblical scholars would say that the construction of the Tower of Babel did not begin until some time in the 1st millennium BC. The story of this video game seems to suggest that the Biblical destruction of the Tower of Babel is a result of the battle between Set and Mathayus. Of course, here the entire tower is destroyed and in the Bible and other historical sources, it either remains simply unfinished or has it's top and base destroyed with the middle left to crumble over time.