ولم يقتصر الإمامُ الترمذي على تلقي العلمِ عن الشيوخ في تِرمذ من أهلها والقادمينَ إليها، بل رَحَلَ في طلب العلم على عادةِ النابهين مِن طلبة العلم في زمانه، فقد ذكر الحافظ المزي في حاشية "تهذيب الكمال" في ترجمة أحمد بن عبيد الله بن سهيل أن رحلة الترمذي كانت بعدَ الأربعين ومئتين.
وقوله: بعد الأربعين ومئتين فيه نظر، فقد ثبت لنا مِن خلال تراجم شيوخِه القدماء الذين أخذ عنهم الترمذيُّ وسَمِعَ منهم أن رحلتَه كانت قبلَ ذلك، فقد سَمِعَ مِن قُتيبة بن سعيد البَغْلانِي المتوفَّى سنة (240 هـ)، وقد عُمَّر، وهو من شيوخ أحمد بن حنبل، وسَمِعَ من إسحاق بنِ راهويه المتوفى سنة (238 هـ)، وسمع علي بن الحسن بن سليمان الواسطي المتوفى سنة (237 هـ)، وسمع من محمد بن عمرو السوّاق البلخي المتوفَّى سنة (236 هـ)، وسمع من أحمد بن محمد بن موسى المروزي السِّمْسَار المتوفى سنة (235 هـ)، كما سمع من جملة شيوخ أُرّخت وفياتهم سنة (239 هـ) و (240 هـ).
وكانت رحلته إلى مدنِ خُراسان الأخرى، فقد دخلَ بُخارى كما صرح غُنْجارٌ صاحبُ "تاريخ بخارى"، ودخل مرو، والري، ثم العراق حيث دخل البصرةَ وواسط والكوفة وبغداد، ثم الحجاز.
وقول الشيخ أحمد محمد شاكر: ولكني لا أظنه دخل بغداد، ومتابعة الدكتور نور الدين عتر والدكتور محمد حبيب الله مختار له