ارتحل الإمام مسلم في طلب الحديث، فكانت رحلاته واسعة، فوصفه النووي أنه أحد الرحالين في طلب الحديث إلى أئمة الأقطار والبلدان، فطلب الحديث في بلده نيسابور وخرسان، فأول سماعه في سنة 218 هـ بخرسان من يحيى بن يحيى التميمي، وإسحاق بن راهوية، وآخرين، وبالري محمد بن مهران الجمال، وأبي غسان، ومحمد بن عمرو زنيجا، وكانت أولى رحلاته الخارجية في سنة 220 هـ وعمره حينذٍ أربعة عشر عامًا، حيث ذهب إلى بلاد الحرمين لأداء الحج، فسمع بالمدينة المنورة إسماعيل بن أبي أويس، وسمع بمكة شيخه القعنبي -وهو أكبر شيوخه- وطبقته، وسمع من سعيد بن منصور، وأبي مصعب الزهري، وبعد أن أدى الحج سمع من الشيوخ في البلاد التي مر عليها، وارتحل مسلم إلى بلخ، والعراق، ورافقه في هذه الرحلة أحمد بن سلمة النيسابوري، ودخل البصرة، ودخل بغداد، فسمع فيها أحمد بن حنبل، وعبد الله بن مسلمة القعنبي، ويحيى بن صاعد، ومحمد بن مخلد، وأكثر عن علي بن الجعد، لكنه ما روى عنه في الصحيح شيئًا، ودخل الكوفة وسمع من أحمد بن يونس، وعمر بن حفص بن غياث، ثم عاد إلى بلدته، وبعد عدة سنين بدأ رحلاته مرة أخرى قبل 230 هـ.