Sultan II. Abdülhamit Han döneminde yaygınlaştırılmaya başlayan Mülk-i İdadilerin birisi 1885 yılında Erzurum'da kurulması kararlaştırılmış, inşaatın 1889 yılında tamamlanmasıyla birlikte eğitim ve öğretime açılmış, 125 yıldır Birinci Dünya Harbi yılları hariç eğitimini aralıksız sürdüren ender kurumlarımızdan biri olmuştur. Başlangıçta beş yıl olarak düşünülen idadi kısa zaman sonra yedi yıla çıkarılarak Fransızca dersi zorunlu dersler arasına sokulmuştur.
İdadi binasının mimari yapısı Milli Mimariye göre yapılması istenmiş ancak örnek bulunamayınca Fransız modeli esas alınarak bugün Şair Nef'i Ortaokulu olarak hizmet veren okul yapılmıştır.
Erzurum İdadisinin ilk müdürü Abdi Namık Bey olmuş, idadinin yıllık giderleri içinde 275.420 kuruşluk ödenek ayrılmıştır. Öğrencileri Leyli Medcani ve Nehari olmak üzere eğitimlerini sürdürmüşlerdi. İdadi ilk mezunlarını 1895 yılında vermiş günümüze gelindiğinde 2014 yılı itibarıyla kırk bininci öğrencisini de mezun etmiştir. Bu rakam bir kurum için oldukça önemlidir.
Mezunları içinde generalleler, profesörler, doktorlar, öğretmenler, milletvekilleri, iş adamları çıkmış, ülke ye hizmet etmeye devam etmiş, etmeye de devam etmektedirler.
1913 yılında ismi değiştirilerek Sultani olmuş bu adla okul 1922 yılına kadar eğitim faaliyetlerine devam etmiştir. Bu süreç içinde müdürlüklerini; Besim Bey, Ömer Lütfü Bey, Fevzi Bey, Muhittin Bey, Said Ödüklü Bey, Osman Fehmi Bey yapmış Sultani olduğunda ise Süleyman Bey, Mehmet Cemal Bey, Hüsnü Olug Bey ve en sonunun da Cevat Dursunoğlu Bey yapmıştır.
1922 yılından itibaren okulun ismi Erzurum Erkek Lisesi olmuş olup bu tarihten sonra müdürlüklerini; Mehmet Cemal, Murat Uras, Arif Şükrü Ögel, Hüseyin Hüsnü, Salim Dündar, Raif Bayındır, Nazif Barkan, Reşat Özbayoğlu, Bahattin Örnekol, Alim Yakın, Mehmet Müftügil, Alaeddin Dursun, Osman Sargın, Mehmet Serin, Raif Akbulut, Necip Çadırcı, Muammer Kılıç, S. Faruk Günay, M.Halis Özsoy, Osman Aktoprak, Selami Güneş yapmıştır.
Erzurum Erkek lisesinin ismi 1940'lardan sonra Erzurum Lisesine dönüştürülmüş, 1969 yılında Deneme Fen Lisesi olarak hizmet vermiş, 1995'lerden sonra Müfredat Laboratuar Lisesi, Erzurum Anadolu Lisesi adlarını almıştır.
Şair Nefi binasında başlayan eğitim 19201'de Kongre binasında devam ederken kısa bir süre İç tedarik Bölge Başkanlığı binasına, 1927 yılından itibaren Nene Hatun Kız lisesi binasına taşınmış ve 1939 yılında yapılan bugünkü binasına taşınarak günümüze kadar gelmiştir.
Ahmet Hamdi Tanpınar, Ziyaettin Fahri Fındıkoğlu, Bahattin Ögel, Remzi Oğuz Arık, Abdurrahim Şerif Beygu, Tahsin Akgün, Murat Uras, Mehmet Müftügil gibi ünlü eğitimcilerin ders verdiği bir eğitim yuvası olmuştur.
Kütüphanesi, laboratuarları, spor salonu ile tarih kokan okulun sonradan ilave edilen ek binası ve konferans salonuyla bir bütünlük arz etmektedir.
2013-2014 yılında 804 öğrenci okumuş ve 204 mezun vermiştir Erzurum Lisesi’nde eski Kültür Bakanı Rıfkı Danışman, eski Adalet Bakanı Nejat Eldem, hattat Fuat Başar ve birçok siyasetçi mezun oldular.
Erzurum Marşının şairi Sıtkı Dursunoğlu, 1918 de şehre giren askeri birlik komutanı öğrencileri dedesi Ahmet Somunoğlu, Fizikçilerin Piri "Fizo Baba" yani Hüseyin Karagöl okulun renkli simalarındandı.
Erzurum Lisesinin ülkeye katkılarla bununla sınırlı olmayıp özellikle Birinci Dünya savaşının ölüm kalım günlerinde Pasinler Ovasında Ruslar ile savaşan askerler gıda götürmek için öğrencilerini seferber etmiş 30 kilo yiyecek dolu çuvalları sırtlarında kış soğuğuna aldırmadan şehit olma pahasına Nebi Hanlarına kadar götürmüşlerdir. Bu kahraman Erzurum Lisesi’nin yatılı öğrencileri saatlerce karda ürüyerek sırtlarında ayaklarında hiç bir şey olmayarak hedefe ulaşmışlar ama büyük bölümü de donarak veya hastalanarak geriye dönememişlerdir.
Tarihte Atatürk’ün, İsmet İnönü’nün ziyaret ettiği, TBMM başkanı Necmettin Karaduman, Milli Eğitim Bakanlarının ve nice bürokratın şeref defterini imzaladığı bir lisemizdir.