Samsun'un en eski orta dereceli okulu olan, eski okul binasının kimin tarafından ,hangi tarihte ve hangi amaçla yaptırıldığına dair resmi ve özel kesin bir bilgimiz yoktur. Ancak Rumlar tarafından"Metropolithane" (Piskoposluk) olarak yaptırıldığı söylenmektedir.
1926-27 ders yılı başında Özel İdare'nin gözetiminde "Nemci Terakki Kız İkmal Mektebi" adı ile eğitim öğretime başlamıştır.
1928-29 ders yılı başında "Kız Koleji" adı altında okul civarında olan bir binada kiralanarak Özel İdare tarafından idare edilmek üzere faaliyete geçirilmiş ise de o yıl yatılı öğrenci alınmamıştır. Kolejin müdürlüğüne İsviçreli bir bayan atanmış, ancak görevine başlamadığı için Milli Eğitim Müdürlüğü tarafından idare edilmiştir.
1929-30 ders yılı başında ayrıca bir "Kız Koleji" açılması uygun görülmeyerek , "Kız Ortaokulu" adıyla Milli Eğitim Bakanlığı'na bağlanarak 1930 yılında ilk mezunlarını vermiştir.
1934 yılına kadar yalnız kız öğrencilerin kabul edildiği okula bu yıldan itibaren erkek öğrenci de alınmıştır. Öğrenci sayısı artan okulda çift öğretim yapılmasına rağmen ana bina yeterli olmayınca şimdiki 19 Mayıs Kütüphanesinin bulunduğu yerde bir bina daha kiralanarak okul olarak kullanılmaya başlanmıştır.
1956-57 öğretim yılında Mithat Paşa Ortaokulu adını alan bu tarihi bina 01.11.1956 yılında baca tutuşması sonucu yanmasına rağmen yazılı evrakın tamamı kurtarılmıştır.
Mithat Paşa Ortaokulu kısa zamanda bugünkü binaya kavuşarak 1967-68 Öğretim yılında Mithat Paşa Kız Lisesi olarak 1982-83 öğretim yılına kadar eğitim ve öğretime devam etmiş olup bu tarihten itibaren okula erkek öğrenci de alınmıştır.
1985-86 öğretim yılında tekrar Mithat Paşa Kız Lisesi durumuna getirilen okulumuzun o yıl lise bölümüne tekrar erkek öğrenci alınmamış ,1986-87 öğretim yılında ise erkek öğrenci kabul edilmiştir.
1992-93 öğretim yılında okulumuz Yabancı Dil Ağırlıklı Lise yapılmış,1996-97 öğretim yılında tekrar genel lise olmuştur. Halen genel lise olan okulumuz ,öğrenci , öğretmen ve idarecileriyle birlikte sevgi,saygı ve bilime dayanan bir anlayışla eğitim öğretim hizmeti vermeye ve geleceğimizin mimarı gençlerimizi yetiştirmeye devam etmektedir.
T.C. MİLLİ EĞİTİM BAKANLIĞI Orta Öğretim Genel Müdürlüğünün 25/02/2010 tarih ve 1687 sayılı yazısı gereği Mithatpaşa Lisesi Mithatpaşa Anadolu Lisesine dönüştürülmüştür.
01/09/2016 Tarihinde Kışla M. Gebi Cad. No:296 Adresine taşınmıştır.
2019-2020 Eğitim Öğretim Yılından itibariyle okulumuz Tepecik Mah. 1559. Sok. No:2 İlkadım/SAMSUN adresine taşınmıştır. Burada eğitim öğretime devam edilmektedir.