Mstsislaw est mentionnée pour la première fois dans une chronique de 1156, comme pour la plupart des villes biélorusses, sa première mention écrite fait office de sa date de fondation. Primitivement incluse dans la principauté de Smolensk, elle prit son indépendance en 1180 et devint alors capitale de la principauté de Mstsislaw.