No final do século XIX, a British North Borneo Company (BNBC) começou a estabelecer colônias em todo o Bornéu do Norte (hoje Sabah). Em 1882, a Companhia fundou um pequeno povoado na ilha de Gaya (Pulau Gaya), que já era habitada pelo povo Bajau. Em 1897, este primeiro assentamento foi queimado e destruído pelos rebeldes Bajaus liderados por Mat Salleh.
Após a rebelião, a Empresa decidiu transferir o assentamento para o continente mais facilmente defendido, em frente a Pulau Gaya. Uma vila de pescadores próxima chamada Api-Api (ver nomes originais abaixo), foi o próximo assentamento da Empresa. Este novo local foi então designado como o principal porto e porto, bem como o terminal da Ferrovia Bornéu do Norte. Foi expandido e renomeado Jesselton, nomeado em homenagem a Sir Charles Jessel, o então Vice-Presidente da Empresa.
Eventualmente, Jesselton tornou-se um importante posto comercial do Bornéu do Norte, negociando borracha, rattan, mel e cera. A nova ferrovia foi utilizada para transportar mercadorias para o porto de Jesselton. As revoltas de Bajau durante esses tempos não foram incomuns, e a empresa trabalhou para acabar com a longa ameaça de pirataria na região.
Jesselton foi arrasado pela retirada britânica no início da Segunda Guerra Mundial para evitar que caísse nas mãos dos japoneses. Após a tomada do Bornéu pelos japoneses, ele foi novamente renomeado Api. Rebeliões contra a administração militar japonesa tiveram lugar em Api. Uma grande rebelião ocorreu em 1943 pelo grupo chamado Kinabalu Guerrillas, formado por habitantes locais. A rebelião foi, no entanto, reprimida pelas forças japonesas, depois que seu líder, Albert Kwok, foi preso e executado em 1944. Nas últimas fases da guerra, o que restava da cidade foi destruído novamente pelos bombardeios aliados como parte da Campanha Bornéu em 1945, deixando apenas três edifícios de pé. A guerra no norte de Bornéu terminou com a rendição oficial do 37º Exército japonês pelo Tenente-General Baba Masao em Labuan, em 10 de setembro de 1945.
Após a guerra, a Companhia Britânica Bornéu do Norte voltou a administrar Jesselton, mas não conseguiu financiar os enormes custos da reconstrução. Eles deram o controle do Bornéu do Norte à Coroa Britânica em 1946. O novo governo colonial escolheu reconstruir Jesselton como a capital do Bornéu do Norte em vez de Sandakan, que também havia sido destruída pela guerra.
Quando Bornéu do Norte junto com Sarawak, Singapura e Federação da Malásia formaram a Federação da Malásia em 1963, o estado ficou conhecido como Sabah e Jesselton permaneceram como sua capital. Jesselton foi renomeada Kota Kinabalu em 30 de setembro de 1968 e recebeu o status de cidade oficial do governo malaio em 2 de fevereiro de 2000.
Etimologia
Kota Kinabalu tem o nome do MonteKinabalu, cerca de 90 quilômetros a leste-nordeste da cidade. O significado e a origem do nome Kinabalu é incerta. Uma teoria sugere que ele significa "viúva chinesa", onde Kina significa "chinesa" (pessoa) na língua Kadazandusun, e balu significa "viúva" na língua malaia. Esta teoria deriva de um conto popular sobre um príncipe chinês que veio à montanha em busca de uma pérola gigante que era guardada por um dragão no topo da montanha. Enquanto ele estava aqui, ele se casou com uma mulher local, mas depois voltou à China e deixou a mulher com o coração partido. Alternativamente, também é argumentado que Kinabalu ou Akinabalu é o nome do dragão que guarda a própria pérola gigante. Outra teoria sugere que o termo deriva do nome Aki Nabalu que significa "lugar venerado dos mortos", no qual, Aki significa "antepassados" ou "avô", sendo Nabalu um nome para a montanha na língua Dusun. Finalmente, há também uma fonte que afirma que o termo teve origem em Ki Nabalu, onde Ki significa "ter" ou "existir", e Nabalu significa "espírito dos mortos".
Kota é uma palavra malaia para um "forte", "cidade", ou uma "cidade". É também usada formalmente em algumas outras cidades da Malásia, por exemplo, Kota Bahru, Kota Tinggi, e Kota Kemuning. Também poderia ser usado informalmente para se referir a qualquer cidade ou vilarejos. Daí em diante, uma tradução direta do nome Kota Kinabalu para o inglês seria "City of Kinabalu" ou "Kinabalu City".
Nomes originais
Além de Jesselton, houve uma série de outras reivindicações quanto ao nome original para Kota Kinabalu. A mais popular, como mencionado acima, é Api-Api, ou às vezes simplesmente Api, que é uma palavra malaia que significa "Fogo". Aparentemente foi nomeada como tal pelos habitantes principalmente de Bajau para denotar o incêndio do escritório administrativo britânico em Pulau Gaya instigado por Mat Salleh, bem como outros incêndios normalmente perpetrados por piratas. Houve, no entanto, alegações de que o nome do escritório foi realmente derivado de um rio próximo chamado Sungai Api-Api. Outra teoria afirma que "Api-Api" é o nome local da árvore comum Avicennia que cresce em abundância ao redor da área. Traduzido para o nome chinês formal Ya Bi (亚庇 yà bì), os Hakkas aqui também adotaram este nome (亚庇, "ah-bi" que se pronuncia em Hakka, dialetos chineses) e alguns ainda usam este nome até hoje. Além do Api-Api, outro nome histórico sugerido foi Deasoka, que significa aproximadamente "abaixo do coqueiro" na língua Bajau. Os habitantes de Bajau supostamente usavam este nome para se referir a uma vila na parte sul da cidade que estava repleta de coqueiros. Outro nome era Singgah Mata que literalmente significa "olho de trânsito", mas pode ser traduzido vagamente como significando "agradável ao olho". É um nome supostamente dado por pescadores de Pulau Gaya que se refere à faixa de terra do que é hoje o centro da cidade de Kota Kinabalu. Hoje, todos estes nomes foram imortalizados em nomes de ruas ou edifícios ao redor da cidade. Alguns exemplos são: Lintasan Deasoka, Api-Api Centre, Jalan Singgah Mata, e Jesselton Point.