On March 3, 1918 Russia, controlled by the Bolsheviks, signed the Brest-Litovsk peace treaty with Germany, in which it gave up control over Ukraine. On March 8 Germans troops reached Bakhmach, an important rail hub, and in doing so threatened the Czech Legion with encirclement. The threat was so grave because captured legionnaires were summarily executed as traitors of Austria-Hungary. Thanks to the Legion victory, the Germans negotiated a truce, during which Czechoslovak armoured trains could freely pass through Bakhmach railway junction to Chelyabinsk.

After the Legion succeeded in leaving Ukraine eastbound, executing a fighting withdrawal, representatives of the Czechoslovak National Council continued to negotiate with Bolshevik authorities in Moscow and Penza to facilitate evacuation. On 25 March, the two sides signed the Penza Agreement, in which the Legion was to surrender all but personal guard weapons in exchange for rail passage to Vladivostok.

However, the Legion and the Bolsheviks distrusted each other. Leaders of the Legion suspected the Bolsheviks of seeking favor with the Central Powers, while the Bolsheviks viewed the Legion as a threat, a potential tool for anti-Bolshevik intervention by the Allies, while simultaneously seeking to use the Legion to manifest just enough support for the Allies to prevent them from intervening on the pretext that the Bolsheviks were too pro-German; and the same time, the Bolsheviks, in desperate need of professional troops, also tried to convince the Legion to incorporate itself to the Red Army. By May 1918, the Czechoslovak Legion was strung out along the Trans-Siberian Railway from Penza to Vladivostok. Their evacuation was proving much slower than expected due to dilapidated railway conditions, a shortage of locomotives and the recurring need to negotiate with local soviets along the route. On 14 May, a dispute at the Chelyabinsk station between legionaries heading east and Magyar POWs heading west to be repatriated caused the People's Commissar for War, Leon Trotsky, to order the complete disarmament and arrest of the legionaries. At an army congress that convened in Chelyabinsk a few days later, the Czechoslovaks – against the wishes of the National Council – refused to disarm and began issuing ultimatums for their passage to Vladivostok. This incident sparked the Revolt of the Legions.