The northern frontier
In the eighth century the imperial court ruled most of western and central Japan, but not the far north of Honshu. The peoples there, whom the court called the Emishi, fought off its advance for generations. Commanders with titles much like sei-i taishōgun were sent against them throughout the century.
Otomaro and Tamuramaro
The first man named sei-i taishōgun in that exact form was Ōtomo no Otomaro, in 794, the year the court moved to Heian-kyō, the city now called Kyoto.
The most famous early holder was Sakanoue no Tamuramaro, appointed in 797. He pushed the frontier north, built a fort at Isawa in 802, and received the surrender of the Emishi leader Aterui the same year. For centuries afterwards Tamuramaro was remembered as the model of a loyal general.
The court in charge
For the next three centuries real power in Kyoto lay with the court nobility, above all the Fujiwara family, who governed as regents for the emperors. This was the age of The Tale of Genji, and the title of shogun mattered little.
Meanwhile the provincial warrior clans, hired to keep order and collect taxes far from the capital, grew stronger than the court that employed them. By the twelfth century two of them, the Taira and the Minamoto, were strong enough to fight over Kyoto itself. That war gave the title its new meaning.