Следующий поединок Мусаси состоялся, когда ему было шестнадцать. В этот раз он победил самурая по имени Тадасима Акияма. Впоследствии Мусаси странствовал по стране, участвовал в поединках и шесть раз принимал участие в крупномасштабных военных действиях. Хотя традиция странствующих воинов была известна задолго до рождения Мусаси, на XVI и XVII века приходится расцвет этого образа жизни самураев. В это время жили многие легендарные личности в истории японских боевых искусств: Камиидзуми Исэ-но-ками, Ито Иттосай, Ягю Дзюбэй и другие.
Мусаси прославился тем, что был, как предполагают некоторые исследователи, первым, кто использовал в поединках одновременно оба самурайских меча, длинный и короткий. Поэтому он называет свою школу Нито-рю (стиль двух мечей). Отсюда же происходит и псевдоним, который Мусаси избрал себе как художник, – Нитэн (два неба). Хотя в настоящее время в Японии по-прежнему есть школа фехтования под названием Нито-рю, нет надежных свидетельств в пользу того, что именно Мусаси был ее основоположником. Известно также, что в поединках с очень опытными противниками Мусаси не пытался использовать одновременно оба меча.
Итак, прежде чем перейти к оседлому образу жизни в возрасте пятидесяти лет, Мусаси провел много лет странствующим мастером, пытаясь усовершенствовать свою технику и выработать собственный стиль. В это время он чуждался общества и направлял все свои силы на поиски просветления на Пути меча. Стремясь к совершенству, Мусаси не щадил себя. Нередко голодный и бедно одетый, он путешествовал по всей Японии под дождем и снегом, не заводя семью и не занимаясь ничем, кроме своего искусства. Предание гласит, что он никогда не ходил в баню, боясь, что враги застигнут его врасплох без оружия, и поэтому вид у него всегда был неухоженный и свирепый.
В битве при Сэкигахара (1600), в которой Иэясу победил войска Хидэеси и стал сёгуном Японии, Мусаси воевал в армии Асикага на стороне Хидэеси. Он выжил в ужасной трехдневной резне, в которой погибло семьдесят тысяч человек, а затем смог избежать участи рассеявшихся остатков армии Хидэеси, подвергавшихся жестоким преследованиям. В 1605 году, когда Мусаси исполнился двадцать один год, он отправился в столицу, Киото, где собирался отомстить семейству Есиока, потомственным учителям фехтования в доме Асикага. Впоследствии сёгун запретил этому семейству преподавать кэндо, после чего оно стало семейством известных маляров и остается таковым вплоть до настоящего времени. Мунисай, отец Мусаси, был частым гостем при дворе Асикага, и в разное время его вызывали на дуэль три представителя семейства Есиока, одного из которых ему не удалось победить.