В июне 1920 года Милян снова встретил Франко в Мадриде и предложил ему место заместителя командующего Испанским легионом. Вначале предложение Миляна не увлекло Франко, потому что его отношения с Кармен были в самом расцвете и еще потому, что в Марокко, по крайней мере на тот момент, было так же спокойно, как в самой Испании76. Но после недолгих колебаний, убоявшись перспективы завязнуть в Овьедо, он согласился. Для Кармен Поло начался трудный период, в течение которого ей предстояло доказать, способна ли она проявить такое же терпение и решимость, как ее муж. Говоря об этом времени восемь лет спустя, она отметила: «В моих мечтах любовь всегда мне виделась озаренной радостью и смехом; но мне она принесла больше печали и слез. Первые мои женские слезы были о нем. Мы были помолвлены, но ему пришлось оставить меня и уехать в Африку для организации первого батальона Легиона. Можете себе представить мое вечное беспокойство и переживания, которые особенно усиливались в дни, когда газеты писали об операциях в Марокко или когда письма задерживались дольше обычного»77.
Формально Легион был основан 31 августа 1920 года под названием «Tercio de Extranjeros». Терсио, или треть — так в XVI веке назывались полки армии Фландрии, которые делились на три группы: воинов-копьеносцев, воинов с арбалетами и воинов с аркебузами. Новое формирование имело также три батальона, или banderas (знамена). Миляну Астраю не понравилось название, и он все время настаивал на «Легионе», что больше нравилось и Франко.
Только что закончилась мировая война, и с добровольцами проблем не было. Двадцать седьмого сентября 1920 года Франко стал командиром первого батальона (primira bandera). Отложив осуществление планов пожить рядом с Кармен Поло, он 10 октября 1920 года на пароме «Алхесирас» вместе с первыми двумя сотнями наемников — сборищем отбросов общества, жестоких, а то и просто жалких людишек — покинул берега Испании. Среди них были и обычные уголовники, включая иностранцев, ветеранов войны, которые не смогли приспособиться к мирной жизни, и активные участники социальных беспорядков в Барселоне. Низенький, хрупкий, бледный двадцативосьмилетний майор Франко со своим высоким голосом не очень походил на человека, который сумел бы совладать с такой бандой.
Смерть была манией Миляна Астрая. Для своих рекрутов он не видел другой стези, как сражаться и погибать. Милян и Франко через всю жизнь пронесли милое их сердцам романтическое представление о Легионе как о последней возможности, предоставленной отбросам общества найти искупление через дисциплину, преодоление трудностей, борьбу и смерть. Это прослеживается в «Дневнике одного батальона» (Diario de una bandera), написанном Франко в первые два года существования Легиона и представлявшем любопытную смесь сентиментальности, духа романтических приключений и полного равнодушия к проявлениям всего звериного в человеке. В своей приветственной речи перед первыми рекрутами истеричный Милян сказал им, что, как воры и убийцы, они были обречены, и только вступление в Легион спасло их. Все более распаляясь, он предложил им новую жизнь, но платой за нее все равно должна была стать смерть. Он назвал наемников «женихами смерти» (los novias de muerto)78. В Легионе царил дух жестокости и бесчеловечности, и Франко полностью нес за это свою долю ответственности, хотя внешне он проявлял себя достаточно сдержанно. Дисциплина в Легионе бьша жесточайшая. Расстрелять могли не только за дезертирство, но и за незначительные нарушения дисциплины79. Пока Франко был заместителем Миляна Астрая, он не позволял себе непослушания, недисциплинированности или нелояльности по отношению к командиру, хотя искушение воспротивиться воле этого маньяка бывало, и весьма сильное80.
По прибытии в Сеуту легионеры всю ночь терроризировали город. От их рук погибли проститутка и капрал гражданской гвардии. При попытке оказать сопротивление убийцам были застрелены еще двое81. Франко вынужден был перебросить свой батальон в Дар-Риффьен, где на восстановленной старинной арке вывели надпись: «Легионеры — в бой, легионеры — вперед навстречу смерти» (Legionerios a luchar, legionarios a morir).