Pada seperempat abad ke-16 Masehi, wilayah Kesultanan Mataram merupakan bagian dari wilayah Kesultanan Pajang. Statusnya sebagai kadipaten dengan penguasanya yaitu Ki Ageng Pamanahan. Setelah Panembahan Senapati berkuasa di Kadipaten Mataram, ia memisahkan wilayahnya dari Kesultanan Pajang dan mendirikan Kesultanan Mataram.[8] Kesultanan Mataram didirikan olehnya pada tahun 1586. Selanjutnya pada tahun 1586 wilayah Pajang sudah menjadi bagian dari kedaulatan Kesultanan Mataram diikuti penyerahan tahkta Pajang oleh Pangeran Benawa kepada Panembahan Senapati. Perkembangan Mataram begitu besar dan kuat sehingga sebagian besar sejarawan setuju bahwa itu telah didirikan selama beberapa generasi perintis Mataram.
Menurut catatan Jawa, raja-raja Mataram adalah keturunan dari Ki Ageng Sela (Sela adalah sebuah desa dekat Demak sekarang). Pada tahun 1570-an, salah satu keturunan Ki Ageng Sela, Kyai Gede Pamanahan dianugerahi kekuasaan atas tanah Mataram oleh raja Pajang, Sultan Adiwijaya, sebagai imbalan atas jasanya mengalahkan Arya Panangsang, musuh Adiwijaya.[9] Pajang terletak di kota Surakarta saat ini, dan Mataram awalnya adalah vasal dari Pajang.[4] Pamanahan sering disebut sebagai Kyai Gede Mataram. Seorang kyai adalah seorang ulama muslim yang berpendidikan tinggi dan cenderung disegani.
Sedangkan di Pajang, terjadi perebutan kekuasaan besar-besaran yang terjadi setelah Sultan Adiwijaya wafat pada tahun 1582. Pewaris Adiwijaya adalah Pangeran Benawa, digulingkan takhtanya oleh Arya Pangiri dari Demak, dan disingkirkan ke Jipang. Putra Pamanahan, Sutawijaya atau Panembahan Senapati, menggantikan ayahnya sekitar tahun 1584, dan dia mulai melepaskan Mataram dari kekuasaan Pajang. Di bawah Sutawijaya, Mataram tumbuh secara substansial melalui kampanye militer melawan penguasaan Mataram atas Pajang oleh Arya Pangiri, dan Pangeran Benawa dengan cepat menggalang dukungan untuk merebut kembali takhtanya dan merekrut dukungan Panembahan Senapati melawan Pajang. Selanjutnya, Pajang diserang dari dua arah: oleh Pangeran Benawa dan oleh Panembahan Senapati. Perang antara Pajang melawan Mataram berakhir dengan kekalahan Arya Pangiri. Pangeran Benawa kemudian naik takhta di Pajang.[9] Selama periode itu tidak ada putra mahkota Pajang yang menggantikan Pangeran Benawa sehingga takhta Pajang diserahkan ke Panembahan Senapati. Kemudian yang menjadi bupati di sana ialah Pangeran Gagak Baning atau adik Panembahan Senapati. Peristiwa pada tahun 1586 ini menandai berakhirnya kerajaan Pajang dan berdirinya Nagari Kasultanan Mataram.
Kebangkitan Mataram
Sutawijaya menjadi pemimpin monarki dengan menyandang gelar "Panembahan" (secara harfiah berarti "orang yang dijunjung"). Dia mengungkapkan sifat pemerintahannya yang ekspansif dan mulai memproyeksasi manuver politiknya sesuai ketentuan, layanan, dan fungsi administrasi ke timur di sepanjang Bengawan Solo.[9] Pada 1590 menaklukkan Madiun, dan berbelok ke timur dari Madiun untuk menaklukkan Kediri pada tahun 1591 dan Ponorogo.[10] Pada saat yang sama ia juga menaklukkan Jipang dan Jagaraga (utara Magetan sekarang). Dia berhasil mencapai timur sejauh Pasuruan. Setelah berhasil menyatukan Jawa, Panembahan Senapati mengalihkan perhatiannya ke Jawa bagian barat, dengan menaklukkan Cirebon dan Galuh, menjadi vasal Mataram pada tahun 1595.[10] Usahanya untuk menaklukkan Banten pada tahun 1597 gagal, dikarenakan kurangnya transportasi air.[10] Panembahan Senapati wafat pada tahun 1601 dan dimakamkan di Kota Gede, sebagai raja Jawa ia berhasil membangun fondasi negara baru yang kokoh. Penggantinya, Raden Mas Jolang atau yang kemudian bergelar sebagai Susuhunan Anyakrawati.[10]
Kontak pertama antara Mataram dan Belanda terjadi pada era Susuhunan Anyakrawati. Kegiatan Belanda pada saat itu hanya sebatas perdagangan dari pemukiman pesisir Jawa, sehingga interaksi mereka dengan wilayah pedalaman Jawa dibatasi, meskipun dibelakang mereka membentuk siasat untuk melawan Mataram. Panembahan Anyakrawati wafat karena kecelakaan sewaktu berburu rusa di hutan Krapyak. Dari peristiwa itu ia dikenal dengan gelar anumerta Panembahan Seda ing Krapyak (Panembahan yang Meninggal di Krapyak).
Masa kejayaan
Anyakrawati digantikan oleh putranya, Pangeran Martapura. Namun Martapura, kesehatannya buruk dan dengan cepat digantikan oleh saudaranya, Raden Mas Rangsang pada tahun 1613, yang menyandang gelar Susuhunan Anyakrakusuma, dan kemudian pada tahun 1641 mengambil gelar Sultan Agung Adi Prabu Anyakrakusuma (Sultan Agung).[10] Kesultanan Mataram di bawah pemerintahan Anyakrakusuma dikenang sebagai puncak kekuasaan Mataram, dan masa keemasan kekuasaan asli Jawa sebelum imperialisme Eropa pada abad berikutnya.
Pada 1641, utusan Jawa yang dikirim Anyakrakusuma ke Arab telah tiba setelah mendapat izin menyandang gelar "Sultan" dari Mekah. Nama dan gelar Islam yang diperolehnya dari Mekah adalah "Sultan Abdul Muhammad Maulana Matarami".[11]
Pada 1645 Sultan Agung mulai membangun Imogiri, sebagai tempat pemakaman, sekitar lima belas kilometer selatan Yogyakarta. Imogiri tetap menjadi tempat peristirahatan sebagian besar keluarga Kesunanan Surakarta dan Kesultanan Yogyakarta hingga sekarang. Sultan Agung wafat pada musim semi tahun 1646, meninggalkan sebuah negara yang ia bangun, membentang cakrawala sebagian besar Jawa, Madura, dan pulau-pulau sekitarnya.