Menurut tradisi, nama "Wajo" merujuk pada pohon ''bajoʼ''{{efn|Umumnya diidentifikasi sebagai tumbuhan dari genus ''[[Macaranga]]''.{{sfnp|Abidin|1985|p=403}}}} tempat penguasa Cinnotabiʼ La Tenribali{{efn|Juga dikenal sebagai La Tenriba atau La Tenribabbareng dalam beberapa naskah.{{sfnp|Abidin|1985|p=399}}}} mengadakan [[kontrak sosial]] dengan ketiga pemimpin di daerah yang disebut Boliʼ, yang kemudian menjadi wilayah inti Wajo.{{sfnp|Abidin|1983|pp=477–478}}{{sfnp|Wellen|2014|pp=25, 114}} La Tenribali ditunjuk untuk memimpin Boliʼ dengan gelar ''batara'' ('langit').{{sfnp|Abidin|1983|pp=477–478}} Menurut riwayat lontara, ''Batara'' Wajo ketiga, La Pateddungi To Samallangiʼ, dipaksa [[turun takhta]] oleh rakyatnya karena kelakuannya yang tidak bermoral. Ia lalu diusir keluar dari Wajo, dan dibunuh dalam perjalanannya oleh seorang bangsawan Wajo.{{sfnp|Abidin|1983|p=478}} Atas prakarsa seorang tokoh Wajo yang bernama [[La Tiringeng To Taba]],{{sfnp|Halim|2016|pp=196–197}} tata negara Wajo kemudian direformasi dengan pendirian sebuah dewan perwakilan. Dewan ini dimpimpin oleh seorang penguasa utama yang diangkat melalui pemilihan, bergelar ''arung matoa'' ('raja yang dituakan'{{sfnp|Wellen|2014|p=174}}). La Paléwo To Palippu dari Béttémpola dipilih oleh dewan sebagai ''arung matoa'' pertama Wajo.{{sfnp|Abidin|1983|pp=479–482}}
Pada masa pemerintahan ''arung matoa'' keempat, [[La Tadampareʼ|La TaddampareʼTadampareʼ Puang ri Maggalatung]] (menjabat sekitar 1491–1521{{sfnp|Abidin|1985|p=575}}), Wajo menjadi salah satu negeri Bugis yang utama.{{sfnp|Wellen|2014|p=28}}{{sfnp|Pelras|1996|pp=112–113}} Memasuki abad ke-16, Wajo telah mampu mencapai posisi yang relatif lebih tinggi dalam hubungannya dengan [[Kerajaan Luwu|Luwu]], salah satu kekuatan utama di Sulawesi Selatan yang mendominasi tanah Wajo pada abad ke-15.{{sfnp|Druce|2009|p=228}}{{sfnp|Andaya|1981|p=21}}{{sfnp|Pelras|1996|pp=113–114}} Bersama Luwu, Wajo memenangkan perang melawan [[Kedatuan Sidenreng|Sidenreng]] di [[Ajatappareng]], hingga memaksa Sidenreng untuk memberikan sebagian wilayahnya di sebelah utara Danau Tempe kepada Wajo.{{sfnp|Druce|2009|p=228}}{{sfnp|Pelras|1996|pp=113–114}} Di bawah kepemimpinan La Tadampareʼ, Wajo juga menyerap sisa-sisa wilayah [[Cina (negeri Bugis)|Cina]], salah satu negeri Bugis awal yang cukup berpengaruh.{{sfnp|Caldwell|Wellen|2017|pp=306, 319}} Keseimbangan kekuasaan di kawasan timur Sulawesi Selatan bergeser kembali pada awal abad ke-16 ketika Bone, negeri Bugis di selatan Wajo, memenangkan perang melawan Luwu dan menjadi kekuatan paling utama di kawasan tersebut.{{sfnp|Wellen|2014|p=28}}{{sfnp|Andaya|1981|p=22}}{{sfnp|Pelras|1996|p=114}} Pada saat yang sama [[Kesultanan Gowa|Gowa]] dan [[Kerajaan Tallo|Tallo]], kerajaan kembar ber[[suku Makassar]] di sebelah barat semenanjung, [[Sejarah awal Gowa dan Tallo#Gowa dan Tallo dari 1511 hingga 1565|mulai mengembangkan kekuasaannya]].{{sfnp|Andaya|1981|p=24}} Pada awal abad ke-16, Gowa bersekutu dengan Bone dalam perang melawan Luwu dan Wajo,{{sfnp|Andaya|1981|p=23}} tetapi pada pertengahan abad ke-16 Gowa dan Bone menjadi lawan dalam perebutan [[hegemoni]] Sulawesi Selatan. Saat itu, Wajo telah jatuh ke dalam [[lingkup pengaruh]] Gowa, dan mendukung Gowa dalam perangnya melawan Bone pada tahun 1560-an.{{sfnp|Pelras|1996|pp=116, 131–132}}{{sfnp|Andaya|1981|p=30}}
=== Persekutuan ''Tellumpoccoé'' dan Gowa-Tallo (1582–1660) ===
