Negerisembilanas apvidus atradies dažādu valdnieku varā, līdz 15. gadsimtā nonāca Melakas sultanātā. Pēc tam, kad 1511. gadā Melaku iekaroja Portugāle, apvidus nonāca Džohoras sultanātā, no kura tas pārņēma matrilineārās mantošanas tradīciju. Negerisembilanas kā patstāvīgas politiskas vienības dibināšanas laikā 18. gadsimta otrajā pusē sākotnēji bija brīva deviņu valdnieku (luak) konfederācija, no kā arī cēlies nosaukums Negeri Sembilan — ‘deviņas ciltis’. Par pirmo Negerisembilanas valdnieku 1773. gadā kļuva minankabavu augstmanis Radža Mahmuds, ko akceptēja Džohoras sultāns. Atšķirībā no citām Malaizijas monarhijām Negerisembilanas valdnieka tituls nav sultāns, bet Yang di-Pertuan Besar — ‘Tas, kurš ir kļuvis par lielo kungu’, un tas ir vēlēts tituls — valdnieku ievēl štata teritoriālo vadoņu padome Undani (Undang Yang Empat).
1874. gadā Negerisembilanas valdnieks piekrita Lielbritānijas protektorātam un 1895. gadā to iekļāva Federatīvajās Malajas valstīs. 1946. gadā Negerisembilana kļuva par Malajas Savienības daļu, bet 1948. gadā — par Malajas Federācijas daļu, kas 1957. ieguva neatkarību. 1963. gadā Negerisembilana kļuva par Malaizijas štatu.