Berdasarkan sejarah, keberadaaan Kota Tanjungbalai tidak dapat dipisahkan dengan kerajaan Asahan yang telah berdiri ± 392 tahun yang lalu. Tepatnya dengan penobatan Sultan Abdul Jalil sebagai raja pertama Kerajaan Asahan di Kampung Tanjung yang merupakan cikal bakal nama Tanjungbalai pada tahun 1620. Asal-usul nama Kota Tanjungbalai menurut cerita rakyat bermula dari sebuah balai yang ada disekitar ujung tanjung di muara sungai Silau dan aliran sungai Asahan. Lama – kelamaan balai tersebut semakin ramai disinggahi karena letaknya yang strategis sebagai bandar kecil tempat melintas bagi orang – orang yang ingin berpergian ke hulu sungai Silau dan sungai Asahan. Tempat itu kemudian dinamai “Kampung Tanjung” dan orang lazim menyebutnya “ Balai Di Tanjung”.
Tanggal 27 Desember yang merupakan hari mangkatnya Sultan Kerajaan Aceh Sultan Iskandar Muda yang merupakan ayahanda Sultan Abdul Jalil, telah dijadikan sebagai hari lahir Kota Tanjungbalai yang ditetapkan berdasarkan Surat Keputusan DPRD Kotamadya Tanjungbalai Nomor 4 / DPRD / TB / 1986 tanggal 25 Nopember 1986.
Kerajaan Asahan pernah diperintah oleh delapan orang raja sejak raja pertama Sultan Abdul Jalil pada tahun 1620 sampai dengan raja terakhir Sultan Syaibun Abdul Jalil Rahmadsyah pada tahun 1933. Raja terakhir mangkat pada tanggal 17 April 1980 di Medan dan dimakamkan di lingkungan Mesjid Raya Tanjungbalai.
Di zaman penjajahan Belanda, pertumbuhan dan perkembangan Kota Tanjungbalai semakin meningkat dan strategis. Kota Tanjungbalai dijadikan sebagai Gementee berdasarkan Besluit G.G. tanggal 27 Juni 1917 dengan Stbl. 1917 Nomor 284. Hal ini sejalan dengan berdirinya perkebunan – perkebunan di daerah Asahan dan Sumatera Timur, seperti H.A.P.M, SIPEF, London Sumatera (Lonsum) dan lain-lain. Pembangunan jalur transportasi seperti jalan, jembatan dan jalur kereta api mempermudah akses ke Kota Tanjungbalai. Sehingga hasil-hasil dari perkebunan dapat dipasarkan dengan lancar ke luar negeri melalui pelabuhan Tanjungbalai. Maka Kota Tanjungbalai berkembang sebagai kota pelabuhan yang diperhitungkan di pantai timur Sumatera Utara.
Pembukaan kantor – kantor dagang berbagai maskapai Belanda di Tanjungbalai pada abad XX, seperti K.P.M., Borsumeij dan lain-lain, maka mulailah bangsa Eropa menetap di Kota Tanjungbalai. Asisten Resident van Asahan berkedudukan di Tanjungbalai yang jabatannya bertindak sebagai Walikota dan Ketua Dewan Kota (Voorzitter van den Gemeenteraad). Maka mulai saat itu Kota Tanjungbalai selain tempat kedudukan Raja, juga merupakan tempat kedudukan Asisten Resident.
Sejak kemerdekaan Republik Indonesia, keberadaan Kota Tanjungbalai sebagai daerah otonom ditetapkan berdasarkan Undang – Undang Nomor 9 Darurat Tahun 1956 (LN Tahun 1956 Nomor 60, TLN Nomor 1092) tentang Pembentukan Daerah Otonom Kota – Kota Kecil dalam Lingkungan Daerah Provinsi Sumatera Utara, nama Gementee Tanjungbalai diganti dengan Kota Kecil Tanjungbalai. Berdasarkan Surat Mendagri Nomor U.P.15/2/3 tanggal 18 September 1956, jabatan Walikota Tanjungbalai terpisah dari Bupati Asahan. Selanjutnya dengan Undang – Undang Nomor 1 Tahun 1957, nama Kota Kecil Tanjungbalai diganti menjadi Kotapraja Tanjungbalai.
Pada waktu Gementee Tanjungbalai didirikan tahun 1917, luas wilayah Kota Tanjungbalai hanya 106 Ha. Atas persetujuan Bupati Asahan melalui Maklumat Nomor 260 tanggal 11 Januari 1958, daerah – daerah yang dikeluarkan (menurut Stbl. 1917 Nomor 641) dikembalikan pada batas semula, sehingga luasnya menjadi ± 190 – 200 Ha ( ± 2 km²). Berdasarkan Sensus penduduk tahun 1980, dengan luas wilayah 2 km² dan jumlah penduduk ± 40.000 jiwa (kepadatan penduduk ± 20.000 jiwa per km²), menjadikan Kota Tanjungbalai sebagai Kota terpadat di Asia Tenggara saat itu.
Selanjutnya dengan terbitnya PP Nomor : 11 Tahun 1984 (LN Tahun 1984 Nomor 12) tanggal 29 Maret 1984, maka oleh Gubernur Sumatera Utara atas nama Mendagri, pada tanggal 5 Januari 1985 telah meresmikan terbentuknya 2 (dua) Kecamatan di Kotamadya Dati II Tanjungbalai, yaitu Kecamatan Tanjungbalai Selatan dan Kecamatan Tanjungbalai Utara.
Kemudian berdasarkan PP Nomor 20 Tahun 1987 tentang Perubahan Batas Wilayah Kotamadya Dati II Tanjungbalai dengan Kabupaten Dati II Asahan, serta Inmendagri Nomor 22 Tahun 1987 tentang Pelaksanaan PP Nomor 20 tahun 1987, maka luas wilayah Kota Tanjungbalai berubah menjadi 6.052 Ha dengan 5 Kecamatan 11 Kelurahan dan 19 Desa. Berdasarkan Perda Nomor 23 Tahun 2001 tentang Perubahan Status Desa menjadi Kelurahan di Wilayah Kota Tanjungbalai, 19 Desa tersebut telah diubah statusnya menjadi Kelurahan. Semenjak itulah di Kota Tanjungbalai terdapat 5 Kecamatan dengan 30 Kelurahan.
Kemudian berdasarkan Peraturan Daerah Kota Tanjungbalai Nomor 4 tahun 2005 telah ditetapkan pembentukan Kecamatan Datuk Bandar Timur sebagai hasil pemekaran Kecamatan Datuk Bandar. Selanjutnya berdasarkan Perda Kota Tanjungbalai Nomor 3 Tahun 2006 telah ditetapkan pembentukan Kelurahan Pantai Johor di Kecamatan Datuk Bandar. Dengan demikian sampai saat ini, Kota Tanjungbalai terdiri dari 6 Kecamatan dan 31 Kelurahan.
Sumber : Bagian pemerintahan