Sejak abad ke-15, kawasan Jesselton berada di bawah pengaruh Empayar Brunei.[10][11] Lewat tahun 1800-an, Syarikat Borneo Utara British (SBUB) mula menubuhkan jajahan di seluruh Borneo Utara.[12] Pada tahun 1882, Syarikat ini telah mengasaskan sebuah penempatan kecil di kawasan yang dikenali sebagai Teluk Gaya yang didiami oleh suku kaum Bajau.[11] Petempatan pertama adalah di Pulau Gaya.[3] Pada tahun 1897, penempatan pertama ini telah dibakar dan dimusnahkan oleh pejuang kebebasan Bajau, iaitu Mat Salleh.[11]

Selepas kemusnahan Pulau Gaya, SBUB memutuskan untuk memindahkan penempatan ke tanah besar yang lebih mudah dipertahankan seperti di Teluk Gentisan (kini Teluk Sepanggar) pada tahun 1898.[13] Walau bagaimanapun, ia didapati tidak sesuai. Pada tahun 1899, Encik Henry Walker, Pesuruhjaya Tanah mengenal pasti tapak 30 ekar (12 he) sebagai gantian bagi Teluk Gentisan.[14] Sebuah perkampungan nelayan yang dinamakan Api-Api (lihat Nama asal dibawah) telah dipilih kerana kedudukannya yang dekat dengan Perkhidmatan Kereta Api Borneo Utara dan merupakan pelabuhan semula jadi yang dilindungi daripada angin.[3] Pusat pentadbiran yang baru ini dinamakan Jesselton[15] selaras dengan nama Tuan Charles Jessel, yang merupakan Naib Pengerusi SBUB pada ketika itu.

Akhirnya, Jesselton menjadi sebuah pos perdagangan utama Borneo Utara, dengan perdagangan getah, rotan, madu, dan lilin giat dijalankan.[3][16] Keretapi baharu telah digunakan bagi mengangkut barang-barang ke pelabuhan Jesselton.[16] Kebangkitan orang Melayu dan Bajau pada masa itu tidak sangat ketara, dan syarikat juga bekerja keras untuk membanteras ancaman lanun yang telah lama berlaku di rantau ini.

Bandar ini telah dibakar oleh pihak British ketika Perang Dunia Kedua bagi mengelakkan ia daripada jatuh ke tangan Jepun.[11][3] Selepas pengambilalihan Borneo oleh Jepun, ia sekali lagi dinamakan Api. Beberapa pemberontakan terhadap pentadbiran tentera Jepun berlaku di Api. Satu pemberontakan utama yang berlaku adalah pada 10 Oktober 1943 oleh kumpulan yang dipanggil sebagai Gerila Kinabalu yang terdiri daripada penduduk tempatan. Tentera Jepun menghentikan pemberontakan ini selepas pemimpinnya, Albert Kwok, ditangkap dan dihukum bunuh pada tahun 1944.[17][18]

Pada peringkat akhir perang, bandar ini dimusnahkan sekali lagi oleh Tentera Bersekutu dengan pengeboman pada waktu siang dan malam untuk tempoh lebih enam bulan sebagai sebahagian daripada Kempen Borneo pada tahun 1945.[11][3] Aksi ini meninggalkan hanya tiga bangunan yang kekal berdiri.[11][3] Perang di Borneo Utara berakhir dengan penyerahan diri rasmi Tentera Darat Jepun yang ke-37 oleh Leftenan Jeneral Baba Masao di Labuan pada 10 September 1945.[19]

Selepas perang tamat, SBUB kembali untuk mentadbir Jesselton tetapi tidak mampu untuk membiayai kos pembinaan semula yang sangat besar. Mereka menyerahkan pengawalan Borneo Utara kepada Mahkota British pada 15 Julai 1946. Kerajaan kolonial baharu telah dipilih bagi membina semula Jesselton sebagai pusat pemerintahan baharu selain daripada Sandakan, yang juga telah dimusnahkan sewaktu perang.[20]

Pada tempoh 1948-1955, sebuah Pelan Pembangunan Semula dan Pembangunan untuk Borneo Utara telah ditubuhkan oleh kerajaan British.[21] Kerajaan British telah meluluskan dana sebanyak £ 6,051.939 – £ 2,232.882 bagi membina semula dan £ 3,819.057 bagi pembangunan baharu.[21] Jalan raya telah dibina, pelabuhan dibersihkan dan lapangan terbang dibaiki. Pembangunan semula pekan dan sektor pertanian juga diberi tumpuan. Roy Edgardo Parry, Pengarah Pendidikan pertama, telah dilantik untuk menyediakan pelan lima tahun bagi pembangunan pendidikan.[21]

Apabila Borneo Utara bersatu dengan Sarawak, Singapura dan Persekutuan Tanah Melayu bagi membentuk Persekutuan Malaysia pada tahun 1963, negeri ini bertukar nama dan dikenali sebagai Sabah, dengan Jesselton kekal sebagai pusat pemerintahan utama.[11] Jesselton telah ditukar namanya kepada Kota Kinabalu pada 30 September 1968 dan menerima status bandar raya daripada kerajaan Malaysia pada 2 Februari 2000.[11]