According to Islamic tradition, the mosque was built by Ibrahim with the help of his son Ishmael. They were ordered by Allah to build the mosque, and the Kaaba contained theirin is supposed to be a model of the house of God in heaven. The Kaaba also contains the Black Stone which supposidely fell from heaven and turned black due to man's misdeeds. The story of Ishmael and his mother's search for water also takes place in the general vicinity of the mosque. In the story, Hagar runs between the hills of Safah and Marwah looking for water for her son, eventually God reveals the Zamzam Well, from where water continues to flow to this day. The episode of Hagar's frantic search for water is emulated by Muslims as they run between the two hills whenever they visit Makkah.
The mosque itself has always been an important part of Arab culture. Even in pre-Islamic days it was a site to pilgrimages by the idol worshipping Arabs who filled the Kaaba with their idols. This episode is seen as a corruption of what the Kaaaba was meant for, and can explain why God sent Muhammad to the people of Makkah, for they had strayed from the path of God. Muhammad's grandfather, Abu Muttalib was a caretaker of the Kaaba, and Muhammad spent much time there in prayer and reflection.
After the Hijra, Muhammad was forced to Medina. Upon his return to Mecca years later, he ritually smashed all the idols in the Kaaba and cleaned it. This began Islamic rule over Kaaba, and the building of a mosque around it. Intially, the mosque was much smaller than it is today. But over time it expanded slowly. Under the Ottomans it grew to the roughly the size of the current courtyard. Under the Saudi regime, the greatest expansion took place along with a modernization. The mosque was greatly expanded to handle the millions of visitors it received during the hajj. It has also been outfitted with modern conveneinces such as air conditioners and escalators. The outside of the current mosque has a beautiful marble facade, and it has three stories, each which can handle thousands of worshippers.