Vilajet Erzurum je osnovan u 16. vijeku, nakon što je Otomanska imperija osvojila Zapadnu Jermeniju, i njegove granice se nisu mijenjale sve do 20. vijeka. Početkom 20. vijeka, površina vilajet aje bila oko 50.000 km2. Provincija je imala 2 sandžaka, 23 distrikta i 154 poddistrikta, kao i 2.866 (ili 2,663) naselja.