As mentioned before, the Satsuma and Choshu hans/clans were vicious rivals for generations ever since sengoku times. There were frequent disputes and wars among the two then most powerful and richest clans in Japan, and that went down well with the Tokugawa shogunate. As long as the two clans were at war, they would be too exhausted and pre-occupied to rebel against the shogunate. Ryoma realised that for the Restoration movement to be successful, there must be some kind of alliance between all the Ishin Shishis all over Japan, and not each acting on his own, refusing to co-operate with each other because of some petty disputes. Together with his bosom friend, Nakaoka Shintarou, he set about persuading both sides to let down their defenses and to do away with their suspicions of each other. He elaborated to Katsura and Saigo how they would be much more powerful in bringing down the Shogunate if they worked together.
It was certainly not an easy task. Though Katsura hated Satsuma, he saw Ryoma's point in that the Choshu needed the Satsuma's might. Most people of Choshu didn't, however. They hated Saigo's guts even more because several years before, when Choshu waged a war on Tokugawa armies, the Shogun sent Saigo to settle the disturbances. Satsuma armies defeated the Choshu regiments utterly and it was a great shame to them. On the other hand, the Satsuma was also very reluctant to work together with Choshu. Ryoma tried to mend up the relations between the two clans, including suggesting Katsura to sell Choshu rice to Satsuma when a prolonged drought occured in Satsuma. He offered to transport the rice via his own shipping company. Although Satsuma later turned down the offer, it was a beginning. Ryoma also arranged firearm trades between the two clans, so as to make them more amiable to each other. After some very, very tough work and persuasions, the two clans finally agreed to work together in order to throw over the Shogunate, and a treaty was signed in 1866. Later that year, Ryoma succeeded in persuading Tosa to join the league as well, and the three clans, Satsuma, Choshu and Tosa, became the main powers of the Ishin movement. Many Meiji officials were of these three clans.
However, after the Ishin movement succeeded and the Meiji era declared, suspicions between the two clans persisted, and well, officials of Choshu and Satsuma origins still often had disagreements with each other. But that's another story. The important point here was that Sakamoto Ryoma, a 'disgrace' to bushido, an uncouth roshi who had been denounced by his own clan, who was looked down by many noble samurais, made the impossible, possible! People all over Japan marvelled at his success and he was a national hero to many.