Phase One: Road to Azov
As history goes, in 1419 Muscowy was a small principality west of Suzdal', a vassal of the Golden Horde. Her relations with neighbors could be better, partially due to the fact that it were the Princes of Moscow who collected the taxes from whole Russia for her Mongol overlords. Besides Moscow itself, the principality included two more provinces: Vologda and Nizhgorod.
In January of 1914 Muscowy canceled vassalization with Golden Horde. However, this was the time when the Horde was struggling for its very survival. The countless rebellions drove the country on the verge of chaos. The Khan did nothing even when Suzdal' followed Myscowy. Only when Ryazan' declared independence the Horde finally reacted. As nomad armies besieged Ryazan', Vasiliy I ordered his army to the rescue. By that time Muscowy was in alliance with Suzdal' and Tver and was prepared to meet her former overlords on the battlefield.
The war lasted less than two years (July 1421 - December 1423). Russian forces took Tambow, Saratow and Bogutjar and were ready to cross Volga and strike at the very heart of the Golden Horde. Luckily they were spared the effort. The rebels broke the government of the Horde and sent the Khan fleeing to the steppes of the east. His successor was eager to make peace with everyone. Muscowy was granted all the land that it conquered during the war. New ruler's Tatar allies were allowed to create independant Khanates of Kazan' and Crimea, while his Russian supporters created an independant state north of Crimea. They called it Southern Rus', but their neighbors were quick to dub it "Ukraine", as it laid on the edge of the three worlds - Catholic, Orthodox and Muslim.
Ukraine was soon admitted to Russian Alliance. So was Tver, which abandoned it during the war to conquer her western neighbor - Pskov. Vasiliy did not hesitate to cement the alliance with royal marriages. He even went further with Ukraine by providing financial aid and guaranteeing her independence. He also took steps to secure his western border by arranging a royal marriage with Lithuania. He planned to continue his drive to the east, but his plans were burried with him in 1425. A new ruler, Grand Prince Vasiliy II "Temny" had ideas of his own.
He too, however, was fond of Southern Russian state of Ukraine. He had a vision of Ukraine being Russian shield against Catholic Lithuania and a launching ground for a strike across the Black Sea. At that time everyone could see that an imperial city of Constantinople is doomed to fall. It was already sacked once by Albanians, but it was the Turks who worried Grand Prince. Any case, be it Catholics or Muslims, could not be accepted by the Orthodox country. Vasiliy's plans went as far as declaring himself a Defender of Orthodox Faith. Capturing Czargrad would help him well in doing so.
The first step, however, was to strengthen Ukraine. And so, in July of 1428, the war was declared on Crimea. Tver and Suzdal' dishonored the alliance, but were re-admitted some time later. Ukrainians gave their full support for this war and were rewarded a year later, when they were given an opportunity to double their territiry with a capture of enemy's only province.
The second step was to capture a sea port for Muscowy as well. With this goal in mind, Grand Prince went to second war (November 1430 - December 1433) with Golden Horde. Again, Mongols had to fight alone, as all their allies deserted them. In 1431 Kazan' Tatars joined the war on the side of their former ally - new Khan. Soon, they were annexed by Suzdal'. This event together with a capture of Samara by Muscowyans broke the back of Mongol resistance. The Khan had to cede Lugansk, Voronezh and Azov, giving Moscow its first access to the sea.
Conclusion: After the end of the second war with the Golden Horde Grand Prince of Muscowy controlled 9 Russian provinces and had access to the Sea of Azov. The plans were made to build Russian first fleet and sail across the Black Sea (Russian Sea in the chronicles of the old times). Muscowy's allies - Tver, Suzdal' and Ukraine - all had grown to the size of two province countries, making it impossible for a potential foe to annex any of them in the course of the war. A trade agreement was reached with Novgorod, securing Muscowy's trade in the region and steps were taking toward the centralization of the state in order to decrease corruption. Needless to say, this was not taken lightly by local nobles. Numerous rebellions fired the countryside of the recently conquered land. All the rebels were drawned in blood. Such was the fate of anybody who opposed the power of Moscow.
First division of the Golden Horde in 1425