Stein llegó a la India en diciembre de 1887, país que convertiría en hogar para el resto de su vida. Pronto le ofrecieron los puestos conjuntos de Jefe del Colegio Oriental y Registrador de la Universidad del Punjab en Lahore. Desde el mismo principio se encontró cómodo en el ambiente británico, en parte gracias a los tres investigadores que encontró al llegar a la capital del Punjab, que acabarían siendo amigos hasta la muerte: el historiador y experto en clásicas P. S. Allen (1869-1933), el arabista Sir Thomas Walker Arnold (1864)-1930) y Frederick Henry Andrews (1866-1957) quien, en aquel tiempo era Director de la Mayo School of Art. Andrews se convertiría más tarde en ayudante de Stein, dedicando largos períodos de su vida a catalogar sus hallazgos.

En la primera década de su carrera en la India, Stein trabajó como filólogo. Recogió manuscritos sánscritos y editó y tradujo la crónica cachemira del siglo XII, el the Rajatarangini. Para la aclaración de los detalles topográficos de la crónica dedicó sus vacaciones a la investigación anticuaria en Cachemira. Más tarde, en compañía de Andrews, prosiguió sus breves expediciones arqueológicas por los alrededores de Cachemira, donde aprendió de Andrews los rudimentos de la fotografía. Este trabajo le capacitó para las largas expediciones arqueológicas en el Asia Central china.

En 1899 fue nombrado Director de la Madrash de Calcuta, pero detentó el cargo solo un año. Sus planes de exploración del Turquestán chino maduraron entonces, y obtuvo el necesario apoyo oficial.