На Олимпиаде 1935 года в Варшаве Алехину уже не удалось стать первым — на первой доске с отрывом в 1 очко выиграл Флор.
В очередной раз произошли изменения в личной жизни. Во время одной из своих поездок он познакомился с Грейс Висхар, вдовой губернатора Марокко, ставшей вскоре его четвёртой женой. Грейс играла в шахматы, выступала в женских турнирах, владела приличным состоянием, но так же, как и сам Алехин, имела пристрастие к алкоголю. Кроме того, Грейс отказалась принять в семью сына Алехина, Александра. Здоровье чемпиона ухудшилось, нервы были расшатаны.
Всё это проявилось в матче на первенство мира с Максом Эйве, начавшемся 3 октября 1935 года. Начав его в обычной для себя уверенной манере, в первых 9 партиях Алехин захватил безусловное лидерство, получил преимущество в 3 очка, казалось, что исход матча предрешён (хотя комментаторы и отмечали, что чемпион играет слишком рискованно). Но после этого чемпион вдруг запил (следует отметить, что эту версию, отражённую во многих изданиях, соперник Алехина Эйве в своих воспоминаниях категорически отвергал) и проиграл несколько партий. Оказавшись в трудном положении, он не смог играть в полную силу, вместо этого впал в депрессию, допустив в результате ещё несколько грубых ошибок. Претендент же играл прекрасно, в полной мере используя все ошибки противника. К концу матча Алехину, казалось бы, удалось собраться, но времени для исправления ситуации уже не осталось. К тому же подвело здоровье. Результат матча: +8–9 =13. Парадоксально (и не умаляя заслуг Эйве), но этот крупный успех оказался единственным в карьере голландского гроссмейстера — он больше не выигрывал ни в крупных турнирах, ни в матчах, и фактически больше никогда реально не претендовал на мировое первенство.
Во время матча с Эйве в СССР, в газете «Известия» была опубликована телеграмма: «Не только как долголетний шахматный работнику но и как человеку понявший громадное значение того, что достигнуто в СССР во всех областях культурной жизни, шлю искренний привет шахматистам СССР по случаю 18-й годовщины Октябрьской революции. Алехин». Эмигрантские газеты реагировали на это крайне недоброжелательно, а после неудачного для Алехина завершения матча с Эйве не упустили случая позлословить об Алехине, который «битым отошёл к Советам». Алехин получил приглашение на международный турнир 1936 года в Москве, но не принял в нём участия.
На турнире в Ноттингеме в 1936 году Алехина снова постигла неудача — он занял лишь 6-е место, проиграв Капабланке, упустив ничью с Решевским и лишь вничью сыграв с двумя явными аутсайдерами.
Униженный поражением, Алехин поставил себе цель во что бы то ни стало вернуть звание чемпиона мира. Критики, которые в 1935 году предсказывали безоговорочную победу Алехина, теперь в один голос говорили, что у экс-чемпиона нет никаких шансов. Кризис 1935-36 годов был воспринят как признак начавшейся деградации. Но матч-реванш 1937 года расставил всё по местам.
Алехин изучил манеру игры Эйве, подошёл к матчу полностью подготовленным как творчески, так и физически, полностью отказался от алкоголя. Эйве же, видимо, предполагал встретиться с тем же Алехиным, который был побеждён два года назад, и уверился в своей правоте, без больших затруднений выиграв первую партию. Но после четырёх ничьих Алехин добился победы, после которой захватил в матче безусловное лидерство. Победа Алехина была зафиксирована после 25-й партии. Счёт в матче — +10-4=11. Удручённый поражением Эйве вынужден был признать: «Алехин восстановил репутацию сильнейшего среди живущих шахматистов и подтвердил веру в то, что он величайший шахматист всех времён».
Предвоенные годы
Из трёх турниров, сыгранных после возвращения чемпионского звания, в Монтевидео, Маргите и Плимуте Алехин победил в двух первых, в третьем разделил 1–2 места. Выступление на АВРО-турнире в 1938 г., где играли 8 сильнейших шахматистов мира, было неудачным (кстати, как и у Капабланки) — +3–3 =8. Ботвинник, также участвовавший в этом турнире, писал: «Нас мотали по всей стране. Перед игрой вместо обеда — два часа в поезде. Пожилые участники — Капабланка и Алехин — не выдержали напряжения». В микроматче с Капабланкой Алехин выиграл со счётом 1,5:0,5. В том же 1938 году возобновились переговоры о матче с Капабланкой, но из-за неприемлемых финансовых условий претендента они снова ни к чему не привели.
Как писал Ботвинник, после АВРО-турнира он направил Алехину официальный вызов на матч за чемпионское звание, и чемпион ответил согласием, но из-за начавшейся вскоре войны этот матч так и не состоялся. Некоторые исследователи (В. Чащихин) оспаривают реальность этого соглашения, но оно было подтверждено самим Алехиным в интервью английскому журналу «Chess» в 1945 году.