Just getting back to this topic, I'm most familiar with the famous Arab medieval travelers Ibn Jubayr and Ibn Battuta. Ibn Jubayr spent around two years in the 1180s on his pilgrimage from al-Andalus to Mecca and back, via Egypt, Iraq, Syria, Palestine, and Sicily. Much of it by sea. His account of 12th century Norman Sicily is especially interesting I think, a relatively rich portrait of Sicily at a time when it still had a mixed Christian-Muslim population.
Ibn Battuta traveled much further for much longer, all the way from Tangier to India, south-east Asia, and China. But he tended to stop in places along the way for extended periods of time, and his account is unreliable at certain points, including with regard to dates. But, to give an example of a fraction of his travels, he is believed to have left New Saray on the Volga north of Astrakhan in December and reached the Indus the following September (the exact years are in doubt, but early 1330s). So about 8 months, via modern-day Russia, Kazakhstan, Uzbekistan, Afghanistan, and Pakistan.