The first time Sumo was ever mentioned in writing was in the Kojiki (The Book Of Ancient Matters) Which happens to be the oldest Japanese document. What the Kojiki says is that the possession of the Japanese islands was determined by a Sumo match between the gods. According to the book, 2,500 years ago, the gods Takemikazuchi and Takeminakata wrestled on the shores of Izumo along the Japan Sea coast in what is now Shimane-Ken, until Takeminakata lost to Takemikazuchi.
Since Japan didn't keep too many records before the 8th Century, we really don't know if Sumo is a native sport to Japan or if it was influenced by similar forms of grappling from Asia and Europe. The first bout recorded that involved humans was written in 720 AD. It said that in 23 BC, men wrestled in the presence of Emperor Suinin (r. 29 B.C.-70 AD) when he is said to have made a special request to Nomi no Sukune, a potter from Izumo to fight Taima no Kehaya, a bully from what is now Nara-ken. Sukune won after grappling for a while and then delivering some devastating kicks to Kehaya's chest. Since then, Sukune has been named the "Father of Sumo."
There are several other legends about Sumo performed in the presence of royalty before they adopted the Chinese writing system in the 7th century. The first took place in 642 when Empress Kogyoku assembled her guards to perform Sumo to entertain envoys from the Paekche court of Korea. The custom of "Tenran-zumo" (Sumo in the Imperial presence) is still carried out, but in a different form.
After the establishment of the first Shogunate in Kamakura from 1185 to 1392, Sumo came to be practiced by the warrior class. Minamoto no Yoritomo, the most famous Shogun of the era, was a huge Sumo fan. Oda Nobunga (1534-82) was particularly fond of Sumo. In February of 1578, he assembled 1,500 wrestlers from across Japan for a tournament held at his castle. Until then, there were no boundaries to the area in which Sumo matches were held. The space was previously designated by the people waiting for their turn to compete. Nobunga was the first person to draw circular boundaries on the ground for the first time. In the Edo period (1603-1867) several Daimyo (Feudal Lords) began sponsoring the strongest wrestlers. Those sponsored by the Daimyo got a big paycheck and Samurai status.
The first professional Sumo was called "Kajin Sumo" which was that it was to be carried out to collect donations to repair shrines, temples, bridges, etc. The money was also used to pay the Rikishi (Wrestlers), many of whom were Ronin (Masterless Samurai). After a while, the money was just used to pay the Rikishi. During the Edo period, a ranking system was and ranking sheets were initiated. This also gave birth to the Heya system. The Heya system states that all Rikishi (wrestlers) belong to a Heya (Stable) under the instruction of one Oyakata (Coach). The Oyakata have the same name as the stable (Example- Takasago Beya would have Takasago Oyakata, Futogoyama Beya would have Futogoyama Oyakata, etc.) The Beya's Okamisan (Oyakata's Wife) would handle the day-to-day stuff in the Heya. There are five Ichimon (Groupings of Heya) in the Association. Currently, there are 50 Heya and 105 Oyakata and two Ichidai (License given to a Grand Champion for a single Lifetime) toshiyori. Except for the Ichidai Stock, Oyakatas pass on their name to their one of their Deshi (students) or they sell it for a large sum of money to another Rikishi.
The First Sumo Exhibition ever given to a outsider of Japan was on Commodore Matthew Perry's trading trip with Japan in 1854. A interesting story is that they presented him with many gifts, some of them being some 200 lb. of rice, each weighing about 135 lb. each. When Commodore Perry's men tried to lift them onto the boat, They weren't able to do it. But then some Wrestlers came by and each on put 2 on each shoulder and placed them on the ship. After this, they held a exhibition for Commodore Perry. He was unimpressed, but he was probably the first foreigner to see Sumo.