Sejarah Kota Tinggi dan perkembangannya dicatatkan bermula dari tahun 1529, iaitu sejak daerah ini mula diteroka oleh Sultan Alauddin Riayat Syah II, pengasas kerajaan Johor yang memerintah dari tahun 1528 hingga 1564. Lokasi pertama yang diterokai baginda dan dijadikan pusat pemerintahan kerajaan Johor Lama adalah di Pekan Tua (Kampung Sungai telor sekarang).
Nama Kota Tinggi mengambil sempena pembinaan lapan buah kota pertahanan oleh sultan-sultan Johor sepanjang persisiran Sungai Johor, iaitu Kota Kara(1529), Kota Sayong(1536), Kota Batu(1540), Kota Seluyut(1564), Kota Batu Sawar(1587), Kota Touhid(1623), Kota Tinggi(1685), Kota Panchor(1716). Sejarawan tempatan bersetuju bahawa dengan mengambil nama sempena pembinaan 'Kota-kota' pertahanan yang semuanya terletak di 'Tanah Tinggi' itu membuatkan nama Kota Tinggi tersurat sebagai nama daerah ini sehingga sekarang.
Dari segi sebutan, tarikh paling awal nama Kota Tinggi disebut adalah merujuk semasa zaman pemerintahan Sultan Mahmud Syah II (1685-1699). Sementara itu, tarikh Sultan Mahmud Syah II mula menjadikan Kota Tinggi sebagai pusat pemerintahan adalah pada tahun 1688, iaitu apabila baginda dibawa berpindah dari Riau ke Kota Tinggi.
Jika merujuk kepada bandar Kota Tinggi, lokasi paling awal diteroka adalah di kawasan Kota Touhid. Sultan Abdul Jalil Syah III ialah sultan yang bertanggungjawab membuka Kota Touhid pada tahun 1623 dan memerintah di situ dari tahun 1623 hingga 1677. Tetaoi sejarawan tempatan bersetuju bahawa, nama Kota Tinggi paling awal atau pertama kali disebut adalah pada tahun 1688 oleh Sultan Mahmud Syah II.
Berdasarkan peristwa dan tarikh-tarikh itu (1528, 1623, dan 1688), tahun 1688 ialah tarikh yang wajar diterima sebagi tarikh Kota Tinggi dibuka dan lokasi berkenaan terletak dalam Kampung Makam.
Selepas tarikh-tarikh itu sehingga negara mencapai kemerdekaan pada tahun 1957. Bandar Kota Tinggi melalui proses pembangunan yang pesat dan menjadi bandar ternama berpandukan sedia ada sekarang.
