كان والد الإمام مسلم - وهو الحجاج بن مسلم - من المشيخة، ومعناه أن الإمام مسلمًا تعلم في بيته كثيرًا، وهو صغير، ولذلك نجده أقبل على سماع الحديث منذ صغره، فكان أول سماع له سنة ثماني عشرة ومائتين في بلدته نيسابور، وأول من سمع منه بها يحيى بن يحيى بن بكير التميمي (ت ٢٢٦ هـ) ثم حج بعد عامين سنة عشرين. وهو أمرد، فسمع بمكة من القعنبي (ت ٢٢١ هـ) فهو أكبر شيخ له، وسمع بالكوفة من أحمد بن يونس (ت ٢٢٧ هـ) وعمر بن حفص بن غياث (ت ٢٢١ هـ) وجماعة، وأسرع إلى وطنه (١).
وله رحلات في كورته نيسابور وفي ولاية خراسان، وفي بلدان العالم الإسلامي فقد رحل - عدا ما ذكر - إلى المدينة، والبصرة، وبغداد، والري، وبلخ، وإلى مصر، واختلف في رحلته إلى الشام.