波兰流亡政府，以及同这一政府保持联系的在波兰国内活动的地下武装部队，对苏联怀有敌意，主要是由于他们认为苏联曾于1939年9月17日从背后攻击了波兰部队，当时苏联政府同德国人合作，再次瓜分波兰。后来由于1939年11月1日和2日苏联最高苏维埃通过两项法令把“西白俄罗斯”和“西乌克兰”(即“两次世界大战之间的波兰”的东部领土，那里的居民大部分为白俄罗斯人和乌克兰人)并入苏联两个相应的共和国，又加深了这种敌意。俄国人侵入两次大战之间的波兰的东部领土时曾俘虏不少战俘，苏联把这些战俘连同苏联占领区的居民大规模流放到苏联，这就使波兰人更为愤慨。
1941年6月22日希特勒进攻苏联，使波兰人对苏联政府的态度发生了急剧变化，正如这个事变导致英国人和美国人态度的变化一样；波兰总理兼总司令西科尔斯基将军在6月23日的一次广播演说中表示，希望俄国宣布1939年9月28日签订的莫洛托夫-里宾特洛甫条约无效。苏联政府起初不愿考虑对这个条约的领土条款作任何修改；但是，由于7月间德国人在军事上一再取得胜利，再加上英国政府的压力，创造了更加有利于同波兰人举行谈判的气氛。经过长时期的并有英国政府代表参加的谈判，波苏两国政府于7月30日在伦敦达成了协议，协议由西科尔斯基和苏联大使i·m·迈斯基签署。
通过这项协议，苏联政府承认纳粹和苏联之间关于领土变动的1939年条约已“失去效力”。苏波两国政府恢复了外交关系，波兰保证将不同任何第三国签订旨在反对苏联的任何协议。苏联在协议中还同意“在苏维埃社会主义共和国联盟的领土上成立一支波兰军队，并由[在伦敦的]波兰政府征得苏联政府同意后任命一位司令指挥，这支军队将隶属于红军最高统帅部，该统帅部内将包括一名波兰军的代表。详细办法待以后的协议中商定。”协议附带的一项议定书表明，苏联政府“对于所有作为战俘或根据其他充分理由而拘留在苏联境内的波兰公民”给予特赦。另一份秘密议定书还表示，所有各项公私要求将在以后的谈判中考虑。
西科尔斯基-迈斯基协议意味着波兰态度的根本转变，这一转变将在整个战争期间使波兰与盟国之间的合作过程变得错综复杂，矛盾重重。在反对纳粹德国的剧烈斗争的情况下，发生着一场波兰的新旧概念之间的冲突。有一些波兰人，特别是军官，他们同毕苏茨基和贝克的波兰有过较深的关系，仍希望看到波兰能强大得足以在普鲁士和俄国之间保持微妙的平衡。这一派人的理想是一个民族主义的波兰，把那个国家传统的贵族社会结构永久保持下去，并试图对它的邻国采取冷淡生硬的不采协态度。他们必然认识到，只有在他们的传统敌人德国和俄国都软弱无力的情况下，才有可能重新建立这样一个波兰。但是，也另有很多人——那些赞同西科尔斯基想法的人和以前的某些反对党的领袖们——他们决心不让独裁或反动的波兰复活，希望波兰在第二次世界大战后成为苏联的朋友，但应该是真正独立的而且具有健全的民主基础。然而，在这场政治斗争中还存在着另一种因素，它注定要产生最深刻的影响。苏联和共产党的领袖们所设想的波兰，大大不同于凡尔赛条约和里加条约所建立的国家。当红军在1944年进入波兰时，人们记得1920年时红军曾进入过波兰，当时的目的是扩展俄国的革命，而且，在毕苏茨基靠着魏刚的帮助把俄国军队赶回去以前，甚至还在比亚威斯托克成立过苏维埃政府。同时人们也记得，波兰对于有争议的东部领土的主权是以1921年的里加条约为根据的，后来西方国家就把波兰对这部分领土的主权含糊地同东欧的现状等同了起来。但是俄国人认为这些领土是在他们处于被胁迫的情况下硬夺过去的，决不承认这是最后的解决。此外，这个有争议的地区的人种地理方面极端复杂的情况，还提出了一个从来没有得到解决的问题。
1939年10月31日，莫洛托夫在苏联最高苏维埃会议上就俄国对外关系发表讲话时，为9月间俄国人的入侵波兰辩解。他说，入侵是为了解放少数民族——白俄罗斯人、乌克兰人和犹太人——他们由于波兰的瓦解而处于无人照料的困境。瓜分波兰的莫洛托夫-里宾特洛甫协定标志着波兰国家的完结——“这个凡尔赛条约的丑恶产物本来就是依靠压迫非波兰族居民而存在的”。英法政府为“恢复以前的波兰国家”而“继续目前的战争”是“荒唐可笑的”。
可见，俄国人是反对1921年的俄波边界的，而波兰人则没有忘记五次瓜分(最后一次近在1939年)，因而对俄国人疑虑很深；但是只要作为他们共同敌人的纳粹德国还拿着武器，双方最好还是撇开这样的问题而共同对敌。然而不难预见，随着战局的转变，象这样根深蒂固的分歧必然会再次出现。
继1941年7月30日在伦敦签订俄波条约之后，华西列夫斯基将军和博胡斯-希什科将军于8月14日在莫斯科又签订了一项军事协定，其中明白地指出，西科尔斯基将军已任命瓦迪斯瓦夫·安德尔斯将军为苏联境内波兰军队的总司令。而且安德尔斯已着手在那里组织一支波兰军队。
安德尔斯在8月间被任命为这支军队的指挥的时候，刚从莫斯科的卢卞卡监狱获释，当时身体很衰弱，据他自己说，这是由于1939年在反击侵略者的战斗中受了八处伤，以及后来在苏联监狱中又受虐待的缘故。在以后的几个月中，当他努力从当初被押在苏联各处的监狱和劳动营里的大批波兰人中组织一支军队时，他受到俄国人的礼遇。安德尔斯得到伦敦波兰政府派驻苏联政府的新任大使斯坦尼斯瓦夫·科特和由博胡斯-希什科率领的来自伦敦的波兰军事使团的协助。在开始时，波兰人被转移到古比雪夫(萨马拉)，这支军队的最初集中地在附近的布祖卢克。从8月到12月，安德尔斯募集到了好几千名在苏联的波兰人，他们那时被特赦释放后，乘德国人向莫斯科进军的混乱时机，利用他们所能够找到的一切运输工具向着古比雪夫这一总的方向迂回曲折地移动。虽然很难说这批波兰人的命运比当时俄国人的遭遇坏多少，但在布祖卢克，条件是非常艰苦的，因为这些新兵在俄国的初冬季节来到这里，都害着病，营养不良，而且长期经受着风吹雨打。安德尔斯在替他的部队搞装备、食品和御寒服装方面遇到不少困难。从一开始，他和科特就同苏联当局在履行特赦和释放波兰公民问题上陷入了一场外交战。据安德尔斯说，在组织这支队伍的初期阶段，波兰人就由于几千名非常需要的军官和军士的失踪而深感不安，这些人从1940年春季起就不知下落。他们寄给苏联政府的查问信没有得到答复，他们就更加担忧了。1941年12月，当西科尔斯基从伦敦到达莫斯科进行视察，并与苏联领导人举行会谈时，又提到了这个问题。安德尔斯陪同他去莫斯科，并亲自向斯大林陈述了他在设法使劳动营中的波兰人得到释放以参加他的军队，以及在为他的部队获得装备和粮食方面所碰到的困难。由于气候寒冷，安德尔斯还要求把他的部队转移到苏联更南一些的地方。在这次会见中，西科尔斯基建议应该让波兰人转移到中东某个地方去——譬如说波斯，那时波斯由英国和苏联共同占领着——他们在那里可以得到英美的给养并在较暖和的气候中训练。斯大林表示他怀疑这是英国的一个花招，西科尔斯基说，为了表示他的诚意，他愿意建议让这支军队留在苏联，如果它能够得到适当的给养和装备的话。虽然波兰人在失踪的军官这一问题上仍没有得到满意的答复，但这次会议在改善波苏关系方面是成功的，斯大林似乎极愿意合作，他答应了波兰人大多数的请求。苏方同意增加波兰军的兵力，答应作进一步努力，以使那些被拘留的波兰人获释，并命令红军参谋部的潘菲洛夫将军负责为苏联境内的波兰军提供军粮和装备。会谈于12月4日结束时，斯大林和西科尔斯基签署了“友好互助”宣言，保证在对德战争及以后的和平时期中都相互合作。第二条写道，为了执行7月30日的西科尔斯基-迈斯基协议，“两国政府将在整个战争期间在军事上相互全力支援，在苏联领土上的波兰共和国武装部队将与苏军并肩打击德国强盗”。
按照斯大林在这次莫斯科会谈中作出的一项决定，这支波兰军队于1942年初从布祖卢克转移到了塔什干附近的扬吉尤尔；同时由科特在12月和1月谈判达成了两项协议，商定由苏联政府向波兰人提供贷款，以维持大大扩充了的波兰军队和救济苏联境内的波兰公民。当时在科特的主持下，向那些因特赦而获得自由的波兰人分配了救济物品，这些东西大都是租借法的物资。1941年12月23日，签订了一项协议，规定在苏联境内，任命十九名外交代表和他们的办事人员，以推进这项工作。与此同时，尽管有了这些较为协调的气氛，苏联当局在1941年12月初重新逮捕了几个波兰领袖，包括两名犹太人社会党的工会活动家艾尔利什和阿尔泰；另有迹象表明在关于前波兰东部领土上非波兰族居民的身分问题上，正在同苏联当局发生一场新的争论。
1942年初，安德尔斯与伦敦的西科尔斯基磋商之后，拒绝了红军和内务人民委员部当局要他分别派几个师到前线去与红军一起作战的请求(他后来说，他不愿把他那些身体疲惫、配备简陋、还没有训练好的部队一支一支地派往前线，因为到了前线，他们很快就会被吞掉而失去作用，他宁可把他们集结在一起，直到他们能够作为一个有机整体而战斗)。据安德尔斯说，“朱可夫将军和潘菲洛夫将军对这个答复明显地不满意。”的确，这个事件预示着波苏关系的转折点，因为苏联领袖显然怀疑波兰人不肯行动是别有原因的。这一拒绝后来被俄国人解释为违反斯大林-西科尔斯基宣言的精神，特别是违反其中的第二条，在这一条里波兰人保证“与苏联武装部队并肩”战斗。从此苏联官员对苏联境内这支波兰军队的意图显然有了怀疑。并且，随着俄国人军事地位的改善，他们就不那么需要同苏联境内的波兰人或伦敦的波兰政府进行合作了；照安德尔斯的说法，俄国当局不再掩饰他们在设法阻挠他组织这支军队了。
1942年3月，波兰人接到通知，说他们的口粮将被缩减到二万六千份(虽然那时他们的兵员有七万人)。斯大林在答复安德尔斯的呼吁的回电中说，采取这个措施，是由于美国参战，因而减少了经远东运到俄国的粮食供应。因此，他说，有必要“减少对不在作战的各个师的供应”，以优先满足正在作战的各个师的需要，但是，如果安德尔斯希望到莫斯科来讨论这个问题的话，就请他来。安德尔斯接受了这个邀请，3月18日，斯大林同意对俄国境内的波兰士兵供应四万四千份口粮，并让安德尔斯把他的军队的其余部分撤退到波斯。苏联当局执行这项决定时有魄力，也很有效率，3月间，在同英国官员磋商之后，就把第一批约四万名士兵和难民经由克拉斯诺沃茨克撤到了波斯。一直到8月间，经过长期交涉，包括安德尔斯乘飞机到伦敦去了一趟(这期间，他在苏联的部下的境况更坏了)，他才终于又使十一万五千名波兰人(包括妇女和儿童在内)撤到了波斯。安德尔斯自己也到了德黑兰。
在撤退时，安德尔斯得到消息说，齐格蒙特·贝林格中校已擅离他在克拉斯诺沃茨克的职守，并带走了他所掌管的全部文件。在德国入侵苏联之前，俄国人还占领着“两次大战之间的波兰”东部那些有争议的领土时，曾有一些波兰军官自愿参加红军，贝林格就是其中之一。1942年初，他因在安德尔斯军队中犯了不服从上级的罪行而被调到克拉斯诺沃茨克。后来他在战争时期作为红军中的一支波兰部队司令员出现时，他的那次逃离职守就显得耐人寻味了。