Одним из важнейших моментов заключенного пакта было соглашение о формировании ряда частей Польской армии на советской территории. Они должны были укомплектовываться из более чем 200000 польских военнопленных, находившихся на территории СССР. Эти части возглавлял бывший кавалерист генерал Владислав Андерс. Вскоре эти войска превратились в еще одну проблему во взаимоотношениях поляков с Советским Союзом. Польские военнопленные представляли собой скопище изнуренных войной и пленом полуголодных оборванных людей. Сформировать из них боеспособные части было очень сложно, тем более что Советский Союз и сам испытывал серьезную нехватку оружия и техники. Кроме того, среди военнопленных значительную долю составляли офицеры при нехватке рядовых. Однако советская сторона настаивала, чтобы польские части как можно скорее приняли хотя бы символическое участие в войне, и требовала от Андерса как можно быстрее сформировать хотя бы одну польскую дивизию и отправить ее на фронт. Наличие такой слабо оснащенной дивизии принесло бы мало реальной пользы и привело бы к гибели многих людей. Советское правительство настаивало, чтобы первая польская дивизия была сформирована уже к октябрю 1941 г., но к этому времени 5-я Кресовская дивизия еше ходила в лохмотьях, а 40 % солдат не имели обуви. Политики рассуждали о единстве и взаимопонимании союзников, а солдаты должны были жертвовать жизнями за интересы чужого государства, которое только что нарушило договор, а теперь отказывалось признать их права на земли, на которых их предки жили столетиями. Андерс, на которого давило НКВД, все же разделял убеждения своих солдат и отказался послать в бой польские части, ссылаясь на нехватку снаряжения.
В ходе переговоров советская сторона признала, что она не в состоянии адекватно укомплектовать все польские части, и было решено переправить некоторые из них в Великобританию и Иран, где их оснащению могла посодействовать английская сторона. Отношения между польской и советской стороной продолжали ухудшаться, тем более что поляки стали открыто обвинять советскую сторону в противодействии формированию их подразделений. В частности, Сталин отказал полякам в праве зачислять в Польскую армию украинцев, белорусов и евреев, имевших до 1939 г. польское гражданство и проживавших на отторгнутых в пользу СССР польских территориях. Казалось, что ситуация уже выходит из-под контроля, но в 1942 г. американские и британские дипломаты смогли убедить Сталина отправить польские части в Среднюю Азию. Благодаря этому Советский Союз получал возможность высвободить шесть пехотных дивизий, выполнявших роль оккупационных войск на территории Ирана совместно с британскими частями. Западные дипломаты уверяли, что в этом случае легче будет оснастить польские части, чтобы затем направить их на борьбу с нацистами — либо на советско-германский фронт, либо куда-то еще. К тому времени советское правительство уже начало открыто обвинять поляков в нежелании сражаться против немцев. Вместе с тем советские лидеры отказывались принимать во внимание какие-либо заявления поляков относительно действий Советов и нацистов по разделу Польши в 1939 г., как и вести разговор о перспективах возвращения захваченных польских территорий, включая важнейший город Львов. К весне 1943 г. на Средний Восток было отправлено около 115000 польских военнослужащих и членов их семей. Это была лишь небольшая часть из полутора миллионов поляков, находившихся в то время в советских лагерях в качестве военнопленных и депортированных лиц, заключенных под стражу в период проводившейся частями НКВД «деколонизации» восточных районов страны.