В 1934 году Гризодубова была зачислена в штат агитэскадрильи им. М. Горького. Здесь она летала на самолете «Орденоносная? Работница?» (деньги на самолет собирали читательницы главного советского журнала для женщин). Голубой самолет Гризодубовой побывал в агитполетах над самыми отдаленными, глухими уголками Союза. Машина Валентины и ее напарницы – Екатерины Слобоженко всегда содержалась в полном порядке. А женщины-летчицы подбирали летные костюмы под цвет самолета: для белого – белый, для голубого – голубой.

С 1936 года Валентина Степановна уже находилась в рядах Красной Армии. В это время Гризодубова начинает бить рекорды – мода тогда была такая. До своего знаменитого перелета на Дальний Восток, о котором пойдет речь дальше, Валентина Степановна поставила пять мировых рекордах на легкомоторных самолетах конструкции Яковлева. Это были рекорды скорости, высоты и дальности полета. В 1937 году Гризодубова была избрана депутатом Верховного Совета СССР первого созыва, в ее копилке уже были государственные награды: за работу в агитэскадрилье в 1936-м ей был вручен орден Трудового Красного Знамени; за выдающиеся достижения в освоении авиационной техники и установление мировых рекордов В. С. Гризодубова в конце 1937 года была награждена орденом Красной Звезды.

Наконец пришел 1938 год. Перед Гризодубовой была поставлена новая задача – побить рекорд дальности полета на тяжелом самолете. В то время он принадлежал француженке Дюперон – 4360 км. Известный летчик Михаил Громов рассказывает, что, когда его вызвали и спросили, может ли Гризодубова справиться с поставленным заданием, он ответил: «Если кто и может, то она». Началась подготовка к полету. Валентина Степановна сама подыскивала своих спутниц. Одной из них сразу стала талантливый штурман Марина Раскова. С ней Гризодубова уже успела совершить один подвиг – перелет по маршруту Москва? Актюбинск. Раскова же, в свою очередь, летала и без Валентины, участвовала в сверхдальнем перелете Севастополь? Архангельск. В последнем перелете командиром экипажа была Полина Денисовна Осипенко. Она родилась в 1907 году в селе Новоспасском на Днепропетровщине в бедной крестьянской семье. Была в ней девятым ребенком. Работала нянькой, батрачила у помещика, плела лапти… После революции смогла поступить на животноводческие курсы, стала работать птичницей в колхозе. «Нам говорили, – вспоминала она впоследствии, – что курица не летает, потому что она не птица». Но однажды возле села совершил вынужденную посадку самолет. Полину поразило, что в экипаже была женщина. Этот эпизод изменил все ее представления. Полина поехала в Качинск, поступила там в летную школу. В газетах стало появляться ее имя как мастера высотных полетов. 2 июня 1938 года мир облетело известие о беспосадочном полете Полины Осипенко, Веры Ломако и Марины Расковой от Черного к Белому морю.

Гризодубова сомневалась, что столь прославленная летчица согласится лететь вторым пилотом, но Осипенко ответила на «пригласительную» телеграмму немедленным согласием.

Тренировались будущие рекордсменки на Ходынском поле. Не все складывалось гладко. Многие не хотели допустить к подвигу женщин, среди которых была строптивая, а потому имевшая немало недоброжелателей Гризодубова. Так, однажды для тренировочного полета женщинам дали самолет ТБ-3, который был совершенно незнаком никому из членов экипажа. Но Валентина Степановна смело вошла в кабину самолета. Ее муж – летчик Виктор Александрович Соколов – незаметно пробрался в самолет и при посадке отодвинул от пульта руку оторопевшей от неожиданности супруги.