Yayasan Masjid Khadijah Malang didirikan oleh Bu Baharudin Jambek, dan Mbah Sacech. Kemudian Sie Pendidikan dibawah naungan Yayasan Masjid Khadijah, mendirikan MTs. Khadijah pada tanggal 11 Januari 1976. Ketua Sie Pendidikan yakni Drs.Mukhlis Usman, Sekretarismya adalah Drs.Rahman Hilmy, dan bendaharanya adalah H.Yahya Oentong. Awal berdirinya bernama Muallimat 6, tahun katanya meniru muallimat yg di Jogja. Kemudian, ditengah perjalanan tahun ke-2 berubah nama menjadi SMP Putri Khadijah. Berjalan sampai tahun ke tiga sampai masuk masa ujian diikutkan rayon di Jalan Bandung hingga lulusan pertama ijazah dengan nama MTs. Khadijah pada tahun 1979.

MTs. Khadijah mempunyai tenaga pendidikan profesional para mubaligh top Kota Malang dan dosen-dosen IAIN Malang. Tujuan berdirinya adalah bercita-cita mencetak pemuda berakhlaqul karimah, pejuang Islam untuk mencetak kader umat yang tangguh serta mampu bersaing di era global baik dalam bidang IMTAQ dan IPTEK. Kepala Madrasah pada waktu itu adalah Drs. Jazuli. Kemudian, pada tahun 1984, Bapak Prof. Dr. Thohir Luth, M.A memegang amanah untuk menjadi Kepala Madrasah hingga tahun 2017. Pada tahun 2018, amanah Kepala Madrasah diberikan kepada Bapak Eko Wardoyo, S.Pd. MTs. Khadijah berlokasi di Jl. Arjuna no 19A, Kota Malang, Jawa Timur.

MTs. Khadijah merupakan lembaga pendidikan Islam modern tingkat menengah pertama di bawah naungan Kementerian Agama Republik  Indonesia yang memadukan kurikulum dari KEMENAG  dan KEMENDIKBUD dan  mengedepankan pembentukan karakter (Akhlaqul Karimah), prestasi Akademik dan prestasi non Akademik,  ketrampilan dalam Tilawah Al-Qur`an, dan perilaku yang Islami. Perpaduan dua kurikulum yang dibarengi dengan karakter yang Islami tersebut kami yakini mampu menyiapkan lulusan yang berkarakter Islami yang berakhlaqul karimah, berprestasi dalam Akademik dan non Akademik serta mahir dalam Tilawah Al-qur`an.