В марте 1940 года Рокоссовского освободили и назначили командовать тем же 5-м кавалерийским корпусом, которым он командовал до ареста. Большинство освобожденных оставили в прежних званиях — комбриг, комдив и др. Рокоссовскому же, в знак особого доверия, в мае 1940 года было присвоено нововведенное звание «генерал-майор». Поскольку его корпус той весной перебрасывался на Украину, к западным границам, новый нарком обороны Тимошенко направил Рокоссовского в распоряжение командующего Киевским военным округом Г. К. Жукова. У Рокоссовского с Тимошенко были давние приятельские отношения (в начале 1930-х будущий нарком командовал 3-м кавалерийским корпусом, а Рокоссовский — 7-й Самарской имени Английского пролетариата кавдивизией, входившей в этот корпус). Именно Тимошенко, командовавший советскими войсками при прорыве линии Маннергейма и попавший в фавор у Сталина, назвал имя Рокоссовского среди тех, кого необходимо освободить из заключения. Позже бытовала легенда, что Сталин при встрече попросил у Рокоссовского прощения за два с половиной года в «Крестах», но это всего лишь легенда — не таким был Иосиф Виссарионович, чтобы у кого-нибудь публично просить прощения.
В черновиках мемуаров Рокоссовский писал:
«Должен сказать, что Сталин был хорошим психологом. Он понимал состояние командующего в тяжелой обстановке и своим теплым отношением, выраженным словами, умел подбодрить, успокоить и воодушевить, а самое ценное, что можно было вынести из разговора с ним, — это чувство большого с его стороны доверия к человеку. Это производило на меня огромное впечатление. Обычно после каждого такого разговора следовало и усиление армии различного рода средствами и людьми. Помощь иногда была очень скромной, но тогда мы были всему рады. Было действительно очень тяжело».
Этот фрагмент мемуаров доказывает, что Константин Константинович понимал, что все в стране, в том числе и применительно к Красной армии, делается по приказу Сталина. Вряд ли в годы войны он продолжал верить, что НКВД мог самостоятельно, без ведома генсека, сфабриковать дело против него, высокопоставленного командира Красной армии.
Теперь Рокоссовский оказался в подчинении у Жукова, который еще в начале 1930-х годов был его подчиненным. Наверное, Константину Константиновичу было немного обидно. Он мог представить себе, каких бы высот достиг, если бы не арест и два с половиной года в тюрьме. Вполне возможно, что он, а не Жуков возглавил бы советские войска в сражениях на Халхин-Голе, благо, что у него был большой опыт службы как в Монголии, так и в пограничных с ней районах советского Дальнего Востока. А после этой победы он вполне мог стать, по примеру Жукова, командующим Киевским особым военным округом или начальником Генштаба. Быть может, после начала Великой Отечественной войны было бы лучше для армии и страны, если бы на месте М. П. Кирпоноса или Г. К. Жукова оказался Рокоссовский. Константин Константинович был уверен, что лучше бы справился с соответствующими обязанностями, чем эти генералы. Не исключено, например, что, в отличие от Кирпоноса, он в начале сентября 1941 года рискнул бы начать отступление войск Юго-Западного фронта из киевского «котла» даже без санкции Ставки и тем самым спас бы значительную часть их от уничтожения. Правда, при этом у Константина Константиновича все равно были бы большие шансы погибнуть, как Кирпонос, или попасть в плен. А на посту начальника Генштаба он, быть может, сумел бы отстоять перед Сталиным ту точку зрения, что не стоит наносить на второй день войны плохо подготовленные контрудары по вторгшимся германским войскам, да еще в условиях господства в воздухе неприятельской авиации. В мемуарах Рокоссовский жестко критиковал решение Сталина и Жукова о нанесении таких контрударов, считая, что они привели только к неоправданным потерям в людях и технике.