По возвращении в Северную Родезию Стив возобновил тренировки по кэмпо. Наставник Стива видел потенциал своего ученика и объяснил Стиву, что у него есть талант к боевым искусствам Востока. Учитель рассказал Стиву, что он слышал об очень сильном мастере каратэ из Японии – Масутацу Ояме, основателе стиля Кёкусинкай. По мнению учителя, этот стиль подошел бы ему. Годом позже учитель умер, и Стив снова отправился в ЮАР, а оттуда в Европу, где провел некоторое время, странствуя из страны в страну, берясь за любую работу, которую мог найти, чтобы оплатить дорогу в Японию. С той поры он жил, путешествуя из одного порта в другой, пока в конце концов не достиг города Манила на Филиппинах. К тому времени он скопил достаточно денег, чтобы оплатить дорогу сначала в Гонконг, а затем – в Японию, город Иокогаму.
В 1962 г. Стив приехал в Токио. Ориентироваться в городе ему было очень тяжело. Стив даже не знал, где находится додзё Кёкусинкай. Он сумел лишь найти дорогу в Хонбу Кодокан, где встретил Дона Дрейгера. Дрейгер, который увлекался изучением различных стилей боевого искусства, рассказал ему о том, что он тренируется в додзё Оямы. Он взял Стива с собой в Икэбукуро, где за зданием местного университета и находилось маленькое додзё Кёкусинкай.
В то время Ояма путешествовал по Америке, поэтому инструктор додзё сэнсэй Куросаки сказал Стиву, что если он хочет изучать Кёкусинкай, то должен ежедневно приходить на тренировки, но только лишь как зритель, до той поры, пока М. Ояма не вернется из своей поездки. Этот период, период наблюдения, но неучастия в тренировках, длился два месяца. Наконец, когда Ояма вернулся в Японию, Дон Дрейгер и Куросаки представили ему Стива и рассказали ему о том, что Стив преодолел многочисленные трудности и проделал долгий путь, чтобы изучать Кёкусинкай. Первыми словами, с которыми Ояма обратился к Стиву, были: «Если ты хочешь изучать Кёкусинкай, то ты должен быть готов посвятить этому всю свою жизнь. В противном случае я не собираюсь тратить на тебя свое время».
Ояма дал Стиву две недели на принятие решения. В течение этого времени Стив посетил штаб-квартиру Шотокан и школу Годзю-рю. Как в школе Шотокан, так и в школе Годзю-рю Стиву сказали, что он в любое время может начать тренироваться. Легкость поступления в эти школы слишком контрастировала с жесткими требованиями школы Кёкусинкай, и это лишь укрепило уверенность Стива в том, что ему следует принять предложение Оямы.
Поэтому, когда спустя две недели Ояма спросил его, принял ли он решение, Стив ответил – да, он принял такое решение. И к его величайшей радости, Ояма сказал ему, что тот может вступить в додзё в качестве ученика. Однако его предупредили, что ему придется начинать все с нуля. Затем он был представлен другим ученикам, среди которых были Сигэру Ояма, Тадаси Накамура, Окада и Фудзихара. Вслед за этим Стиву принесли кимоно школы Кёкусинкай и предупредили его о том, что тренироваться он должен каждый день, не пропуская ни одного занятия. И даже в случае болезни Стив не имел права пропустить тренировку. Если же он пропустит хоть одно занятие, то ему уже никогда не вернуться в додзё.
Помимо тренировок, которые проходили с 6 до 10 часов вечера все семь дней в неделю, у Стива были определенные ежедневные обязанности. Он должен был следить за чистотой кимоно сэмпаев; за тем, чтобы пол в додзё был безупречно чистым как до, так и после тренировок. Помимо этого, ему приходилось поддерживать чистоту в туалетах. Такая работа была естественной обязанностью каждого ученика.
Поначалу в додзё со Стивом обходились очень грубо. Но спустя некоторое время японцы приняли его в свои ряды.
Кумитэ в додзё всегда было полноконтактным, но, несмотря на многочисленные травмы, Стив продолжал тренировки. Спустя год ежедневных тренировок Стив стал обладателем зеленого пояса, что соответствовало 3 кю. В конце второго года он получил коричневый пояс. Однако черный пояс (1-й дан) Стив получил лишь со второй попытки. Чтобы получить 2-й дан, Стив тренировался очень напряженно, и его усилия оказались не напрасными. Первая же попытка стала успешной.
Во время пребывания в Японии Арнейлу приходилось работать в разных местах, чтобы добыть себе средства к существованию. Он работал моделью на подиуме, позировал для олимпийских плакатов, снимался в кино.
Однажды Ояма вызвал к себе Стива, который к тому времени был обладателем 2-го дана и сказал, чтобы тот приготовился к испытанию хякунин-кумитэ – бой со 100 противниками. В те годы правила испытания были очень жесткими: полный контакт, разрешались любые удары (в том числе в лицо), в случае нокдауна испытуемый должен был подняться за пять секунд. До Стива испытание пытались пройти несколько учеников, но никому из них это не удалось. Среди соперников, с которыми пришлось сражаться Арнейлу, были и сильнейшие бойцы, такие как Накамура Тадаши и Ояма Сигору. Тем не менее он выстоял и навсегда вошел в историю Кёкусинкай.
