From the Super Mario Wiki
The Sphinx, more precisely called the Great Sphinx of Giza (Arabic: أبو الهول, Abū al Hūl, Arabic for "The Terrifying One"), is a monument near Cairo, Egypt with the head of a human and the body of a lion. One of its most striking features is its missing nose, the reason for which is still dubious. The Club Nintendo comic "Mario's Picross" implies that Mario is accountable for it.
The Sphinx made its first appearance in the Mario franchise in the game Mario is Missing! as one of three landmarks Luigi visits is Cairo. In the game, the Klaft of the Sphinx (its hood) was stolen by Koopa Troopas. Luigi's task is to find and return it by answering questions about the Sphinx's name, location, and appearance. The mayor of Cairo offers a prize of 1,750 dollars for the one who returns the artifact.
In the NES version of Mario's Time Machine, the Sphinx appears as a background object in the Egypt area of 31 BC.
In its latest appearance so far, the Sphinx was seen in "Mario's Picross", a comic published in the German Club Nintendo magazine. In this story, Mario travels to Egypt, but gets pushed off the plane by Bowser. Luckily for Mario, he is able to grab onto a rock spur, which however turns out to be the nose of the Sphinx. It breaks off and Mario falls down. Some Egyptians observe this accident and get angry at Mario, calling him a "nose-breaker" and a "philistine" and chasing him. His attempt to escape fails, so he gets arrested.
Pamphlet Information from Mario is Missing!
The man-faced lion statue was named the Sphinx by the ancient Greeks. A sphinx is a mythical monster who liked to ask riddles, then kill those unfortunate enough not to know the answer. The great Sphinx was carved from one enormous piece of lime=stone, 240 feet long and 66 feet high. Later, the Ottoman Turks used the cat for target practice. Its nose and King Tut-style beard were knocked clean off its face. The original name meant "lord," and it is today presumed that the Sphinx was built to guard the great Pyramids that stand behind it.