Соревнование, побудившее его вернуться, проходило в Гаване и открывалось в августе 1965 года. После катастрофы на Кюрасао, как он сам называл тот турнир, это было первое появление Фишера на международной арене. Для американца участие в Мемориале Капабланки было дипломатическим вызовом. Турнир проходил через несколько лет после фиаско в заливе Свиней и кубинского ракетного кризиса. Контакты между Кубой и США были сокращены, и, когда Фишер обратился в Госдепартамент за разрешением посетить Кубу, ему решительно отказали.
Вместо того чтобы бороться с американской бюрократией, Фишер нашёл другой выход и предложил играть по телексу (некоторые утверждают, что идея эта принадлежит кубинскому шахматному организатору Хосе Луису Баррерасу). Такое решение обходилось кубинцам в 10 тысяч долларов. Однако стремление Фишера к контролю оказалось недооцененным. Перед началом турнира он прочитал, что Кастро назвал участие Фишера пропагандистской победой. Фишер немедленно послал кубинскому лидеру телеграмму, в которой заявил, что отказывается от участия: «Я мог бы принять участие в турнире только в том случае, если бы вы немедленно прислали мне телеграмму с заверением, что ни вы, ни ваше правительство не попытаются нажить политический капитал на моем участии в турнире».
Для изучающих психологию Фишера ответ Кастро представляет большой интерес, поскольку кубинский лидер наотрез отказался следовать его указаниям. Куба, ответил он, не нуждается в подобных «пропагандистских успехах». «Если вы испугались, то было бы лучше придумать другие отговорки или иметь мужество остаться честным». Фишер согласился играть и с трудом добрался до второго места.
В январе 1966 года он в седьмой раз стал чемпионом США, получив тем самым право участвовать в межзональном турнире в Тунисе, в городе Сусе. Это была уже его вторая попытка достичь своей главной цели — титула чемпиона мира. Полгода спустя в Сайта-Монике (США) прошёл двухкруговой турнир, в котором принимал участие чемпион мира Тигран Петросян вместе с поверженным претендентом Борисом Спасским. Первая половина соревнования сложилась для Фишера очень плохо, он проиграл три партии кряду, в том числе Спасскому. Однако, как это часто бывало, ему удалось преодолеть спад, собраться с силами и начать подъем. В предпоследнем туре он снова встретился со Спасским. На этот раз Фишер свел партию вничью — он всё ещё не мог победить русского, — и Спасский занял первое место, а Фишер пришёл вторым.
Фишер и Спасский сошлись за доской ещё раз во время шахматной олимпиады на Кубе в ноябре 1966 года. Тогда произошёл инцидент почти на дипломатическом уровне, когда советская сторона отказалась поставить время проведения матча в зависимость от распорядка религиозной жизни Фишера. В конечном итоге матч СССР — США перенесли, и сотни зрителей наблюдали за тем, как Фишер и Спасский добавили в свою копилку ещё одну ничью. На тот момент они сыграли друг с другом четыре раза: Спасский дважды победил, две партии кончились вничью. Во время олимпиады Кастро и Фишер дружески общались между собой, словно трений между ними никогда не было.
Межзональный турнир 1967 года проводился в отеле «Сус-Палас». То, что произошло тогда, до сих пор вызывает споры. Фишер был фаворитом, и организаторы сделали всё, чтобы обстановка отвечала его требованиям, включая дополнительные лампы за столом и составление расписания туров таким образом, чтобы и Фишер, и Решевский были свободны от игры в течение суток с начала вечера пятницы и во время религиозных праздников. Тем не менее турнир потонул в конфликтах. Фишер оказался чрезвычайно чувствителен к шуму и суете, потребовав однажды, чтобы из зала удалили фотографов. Хотя Бобби шел в лидерах, в середине соревнования он, обиженный тем, что ему не дают дополнительный выходной день, внезапно покинул турнир и уехал в город Тунис.
Назавтра Фишер получил ноль за неявку на партию с советским гроссмейстером Айваром Гипслисом. Секретарь американского посольства отправилась на встречу с ним вместе с президентом Тунисской шахматной федерации, прося Фишера вернуться... В следующем туре он должен был играть со своим старым противником Сэмюэлем Решевским. Решевский смотрел, как на часах Фишера медленно заканчивается время, убеждённый в том, что получит очко без игры, однако за пять минут до истечения контрольного срока Фишер все-таки появился в зале и с невероятной скоростью начал делать очень точные ходы!Психологически сломленный Решевский не был в состоянии играть и быстро капитулировал, несмотря на громадное преимущество во времени. Возмущённый американский ветеран ходил по другим участникам с петицией, протестующей против такого поведения Фишера.