After the Soviet invasion of Poland in 1939 the Soviets effectively broke off diplomatic relations when they withdrew recognition of the Polish government at the start of the invasion. The diplomatic relations were however re-established in 1941 after German invasion of the Soviet Union forced Stalin to look for allies. Thus the military agreement from August 14 and subsequent Sikorski-Mayski Agreement from August 17, 1941, resulted in Stalin agreeing to declare all previous pacts he had with Nazi Germany null and void, invalidate the September 1939 Soviet-German partition of Poland and release tens of thousands of Polish prisoners-of-war held in Soviet camps. Pursuant to an agreement between the Polish government-in-exile and Stalin, the Soviets granted "amnesty" to many Polish citizens, from whom a military force was formed. Stalin also agreed that this military force would be subordinate to the Polish government-in-exile. A Polish Army on Soviet soil was born.
Polish military leader, General Władysław Sikorski, nominated General Władysław Anders - one of the Polish officers held captive in the Soviet Union - as commander of this new formation. The first commander, General Michał Tokarzewski, began the task of forming this army in the Soviet town of Tockoje on August 17. The commander chosen by General Władysław Sikorski to ultimately lead the new army, General Władysław Anders, had been just released from the Lubyanka prison in Moscow, on August 4, and did not issue his first orders or announce his appointment as commander until August 22.
The formation begun organization in Buzuluk area, and recruitment begun in the NKVD camps for Polish POWs. By the end of 1941 25 000 soldiers (including 1 000 officers) were recruited, forming three infantry divisions: 5th, 6th and 7th. Menachem Begin was among those who joined. In the spring of 1942 the organizing formation was moved to the area of Tashkent, 8th was also formed.
The recruitment process met several obstacles, particularly the case of significant numbers of missing Polish officers, the dispute with Soviets over whether non-ethnic Poles and citizens of the Second Polish Republic (Jews, Belarusians, Ukrainians) were eligible for recruitment, Soviet assigning low priorities to logistics of this project and refusal to allow volunteers to leave USSR and join already existing and fighting Polish Armed Forces in the West. Another problem was that the Soviet administrators of some labour camps and gulags were not too willing to release the Poles as they required the slave labour to meet their own production quotas.
In the second part of 1942, during the German Caucasus offensive (most notable part of which was the Battle of Stalingrad), Stalin agreed to use the Polish formation on the Middle Eastern front as a military occupation force in Iran after the Anglo-Soviet invasion of Iran; and the unit was transferred across the Caspian Sea to the port of Pahlavi (known today as Bandar-e Anzali), Iran.
After the arrival in Iran, more men were transferred later that summer, to the end of August, by the overland route from Ashkhabad, Turkmenistan (then part of the USSR) to the railhead in Mashhad, Iran. As such, the unit passed from the Soviet control to that of the British government, and as the Polish Second Corps joined the Polish Armed Forces in the West. About 41 000 combatants and 74 000 civilians - Polish citizens - were able to leave USSR with the Anders Army, joining the British High Command in the Middle East, traveling through Iran, Iraq and Palestine.
When the Anders Army reached the latter, most of the Jewish soldiers deserted the regiment and joined the veteran settlement there. After some time the mass desertion of the Jewish soldiers was called the "Anders Aliyah". Despite calls from British authorities, Polish army had not pursued Jewish deserters, except for few smoke screen actions.
The Polish Jews in the Anders Army had additional goals apart from fighting the Nazis. When the Anders Army left the Soviet Union on its journey towards the Middle East, families of the soldiers and groups of Jewish children, war orphans, joined the Jewish soldiers. After arriving in Tehran, Iran, the children were transferred into the hands of the emissaries who brought them to Palestine as the "immigration of the children from Tehran."
The soldiers who deserted the Anders Army, thanks to their army expertise, contributed to the defense of the Jewish settlement in Palestine, and later on also fulfilled the important role of laying down the foundations of the Israel Defense Forces.