The Hebrew University’s academic tour to Mongolia in August 2010 was the trigger for this article, in which the main sites from the tour are described, together with their historical background. Tracking the connections between Mongolia and the Middle East, the article then describes the Mongols’ own tours of the Middle East - their invasions, conquests and rule during the thirteenth and fourteenth centuries. Then, following the trail back to the steppe, the article touches upon Islam in Mongolia from three aspects: the treatment of Islam and the spread of its lexicon through the Mongolian language; the Mongol-Turkic connection; and the Kazakh minority in the modern Mongolian state.