Здесь в 1919 г. он попал под подозрение чекистов, которые обвинили его в связях с белогвардейской контрразведкой. После недолгого суда будущий чемпион мира был приговорен к расстрелу. За два часа до приведения приговора в исполнение известному одесскому шахматисту Вильнеру удалось дозвониться до председателя Реввоенсовета Украины Раковского, и тот предписал немедленно освободить Алехина. Вернувшись в Москву, чудом избежавший смерти шахматист выдержал экзамены в Государственную студию киноискусства. Однако киноактером он так и не стал, а в мае 1920 г. подал заявление об устройстве на работу в Московский уголовный розыск.
В течение девяти месяцев, вплоть до середины февраля 1921 г., Алехин работал следователем главного управления милиции. Одновременно он принимал активное участие в подготовке первого шахматного чемпионата Советской России, который состоялся в октябре 1920 г. Алехин занял в нем первое место. Эта победа как бы подвела итог большой полосе в его жизни. Для него стало ясно, что он превосходит соотечественников в искусстве шахматной игры и что дальнейший рост его мастерства и исполнение мечты о восхождении на шахматный Олимп в условиях России невозможны. Тогда у Алехина и родилась мысль об эмиграции на Запад. Он стал сотрудничать в качестве переводчика в Коминтерне и в марте 1921 г. женился на швейцарской социалистке Лизе Рюэгг, которая была старше его на 13 лет. В апреле они выехали за границу. Как раз в эти дни Капабланка одержал победу над Ласкером и стал третьим в истории шахмат чемпионом мира.
Поселившись во Франции, Алехин начал активно участвовать во всех международных турнирах. Главной целью его был матч с Капабланкой. Но путь к шахматной короне оказался непростым. Международная шахматная общественность вовсе не рассматривала Алехина как претендента на мировое первенство. В качестве таковых выступали экс-чемпион Ласкер и старый противник Алехина Рубинштейн. Чтобы подкрепить свои претензии, Алехин старался не пропускать ни одного крупного шахматного турнира и, переезжая из одной страны в другую, записывал в свой актив все новые победы. В 1922 г. в Лондоне состоялся 17-й конгресс Британского шахматного союза, на котором Алехину впервые довелось скрестить шпаги с новым чемпионом мира. Партия окончилась вничью. Но Капабланка по сумме очков занял первое место, а Алехин — второе.
Выиграв большинство европейских турниров, Алехин в 1923 г. отправился завоевывать Америку. Свое турне он начал в Канаде, дав в Монреале сеанс одновременной игры вслепую на 21 доске. Затем он отправился в США, где за короткий срок дал около сотни партий. Всеобщее внимание привлек его матч против десяти сильнейших шахматистов Балтимора (7 партий он выиграл, три сыграл в ничью). О «европейском чемпионе» заговорили многие американские газеты. На повестку дня встал его матч с чемпионом мира. Однако на Нью-йоркском турнире весной 1924 г. Алехин неожиданно оказался лишь на третьем месте. В этом состязании приняли участие сильнейшие шахматисты планеты, и опять, как десть лет назад в Петербурге, первым оказался Ласкер, вторым Капабланка и третьим Алехин. Алехину пришлось на время отказаться от претензий на мировую шахматную корону.
В 1925 г. Алехин выдержал в Сорбонне экзамен на степень доктора права.
Экзамен потребовал от него много сил, и поэтому Алехин почти не участвовал в турнирах. Но с начала 1926 г. он опять ринулся в бой. Добившись победы на нескольких европейских конгрессах, он отправился в Южную Америку Его успехи здесь имели не только спортивный характер Президент Аргентины Альвеар, покоренный талантом Алехина, объявил, что согласен спонсировать его матч за обладание мировой короной (по существовавшим тогда правилам, претендент должен был обеспечить призовой фонд в 10 тысяч долларов). Алехин отправил вызов Капабланке, и в сентябре 1927 г. в Буэнос-Айресе начался давно ожидаемый «матч титанов» — битва за обладание шахматной короной.
По предварительной договоренности, он должен был играться до шести побед без учета ничьих.
Алехин находился в тот момент в великолепной форме и выиграл первую партию. Правда, в третьей партии Капабланка отыграл очко, а в седьмой вышел вперед. Чемпион мира воодушевился, но его вдохновение разбилось о железную твердость Алехина, который три следующих партии упорно сводил к ничьей. Одиннадцатая партия, в которой Алехин поставил мат при четырех ферзях на доске, стала переломной во всем матче. Капабланка был сломлен этим поражением и, так и не сумев восстановить игру, проиграл 12-ю партию.