Menurut seorang ahli sejarah tempatan, Cikgu Hassan (Allahyarham Tuan Haji Hassan bin Muhammad),Segamat merupakan sebuah daerah paling tua di negeri Johor yang kaya dengan sejarah silamnya lalu ianya digelar "Daerah Lagenda".

Sejarah silam daerah Segamat sering dikaitkan dengan kehebatan kerajaan Malim Dewa yang kononnya pada suatu masa dahulu pernah wujud di satu kawasan luas merintangi Kuala Muar hinggalah ke hulu daerah Segamat. Menurut cerita orang tua-tua [nyatakan menurut siapa?] Putera kepada Raja Malim Dewa iaitu Raja Malim Deman pernah mencintai seorang Puteri yang bernama Puteri Santan Bertapis. Malangnya, Puteri yang digilakan oleh Malim Deman itu telah dibawa lari oleh seorang Putera dari kayangan. Kegagalan untuk mencari Puteri tersebut telah menyebabkan baginda membuat satu sumpahan iaitu selagi Puteri yang dicintainya itu tidak ditemuinya maka daerah Segamat akan dilanda banjir. Dengan demikian, daerah ini telah dikenali sebagai "Daerah Sumpahan Malim Deman"[perlu rujukan]. Selain itu, terdapat peristiwa penting iaitu sekitar tahun 1511, Bendahara terakhir Melaka, Bendahara Tepok dan para pengikutnya berundur ke Johor setelah kejatuhan Melaka ke tangan tentera Portugis pimpinan Alfonso de Albuquerque. BendaharaTepok yang uzur dan para pengikutnya berhenti berehat di satu lubuk sungai di kawasan tersebut dan mandi di sungai tersebut untuk menyegarkan diri Bendahara Tepok. Setelah mandi, beliau berkata, "Segar amat badanku ini!", dan seterusnya menamakan sungai tersebut sebagai Segar Amat, yang kemudian berubah menjadi Segamat.Selain itu,nama segamat diambil ketika Bendahara Tepok mengarahkan pembantu kanannya iaitu Selamat Gagah untuk membawanya melarikan diri dengan perkataan Segera Mat,Segera Mat. Namun demikian, nama tersebut hanya diguna pakai pada sungai tersebut sahaja. Petempatan yang seterusnya menjadi pusat bandar Segamat asalnya dipanggil Rantau Panjang. Segamat juga disebut sebagai "Rantau Panjang" dalam abad ke-18. Ini ada kaitannya dengan keadaan muka bumi sekitar kawasan sungai Segamat pada masa itu. Menurut orang tua-tua, pada masa dahulu kawasan tebing sungai Segamat begitu lurus dengan pasir di tebingnya halus. Apabila terkena sinaran matahari, sepanjang tebing sungai kelihatan seperti hamparan permaidani putih. Air sungainya yang jernih dan berkilau-kilauan menambahkan lagi keindahan kawasan sekitar itu.

Orang-orang Segamat suka berkunjung ke sebuah kawasan bernama Pasir Jenaling untuk berkelah. Ia merupakan sebuah kawasan yang airnya jernih and pasirnya putih berhampiran dengan pengkalan Esah (sekarang terletak di belakang Pawagam Cathay/Sri Genuang). Orang-orang luar yang datang ke Segamat melalui sungai akan berhenti di pengkalan Esah di mana terdapat pokok-pokok Jambu and leban ditebing sungai. Keadaannya yang condong telah menamakan Segamat sabagai "Jambu Condong" dan "Leban Condong".[3]

Menjelang penghujung abad ke-19, 4 daerah asal Johor mempunyai beberapa daerah kecil, contohnya daerah asal Muar mempunyai 4 daerah kecil - Parit Jawa, Chohong, Lenga dan Segamat. Pegawai Daerah Kecil Segamat yang pertama adalah Encik Menthol bin Haji Ahmad. Pada tahun 1933, daerah penuh Segamat ditubuhkan setelah persempadanan semula oleh kerajaan Johor bagi memisahkan 4 daerah asal (Muar, Batu Pahat, Johor Bahru dan Sedili) kepada 8 daerah (sebelum persempadanan tahun 2008 yang menambah daerah Kulaijaya dan Ledang untuk membentuk 10 daerah).