Pada akhir tahun 1800, sebuah pondok kecil lagi usang dijadikan sekolah oleh penduduk kampong. Bertempat di hujung Pekan Kota ( Pasar Lama ) pondok kecil beratap nipah, tiada berdinding dan bercantaskan tanah, pondok ini diberi nama Sekolah Orang-orang Melayu Kota. Memandangkan pondok ini kecil dan tidak selamat untuk digunakan, pada tahun 1904 ( 4 tahun berikutnya) penduduk kampung dengan semangat bergotong-royong berjaya mendirikan sebuah bangunan kecil untuk dijadikan sekolah dengan keluasan berukuran 70 kaki panjang dan 30 kaki lebar. Sekolah ini dikhaskan untuk pelajar lelaki manakala perempuan ditempat di Ulu Gadong.  

      Inilah coretan kisah sebenar penubuhan awal sekolah di kawasan Kota ini, yang mana pihak warga sekolah begitu bersungguh-sungguh berusaha merisik, menjejaki mereka yang mengetahui kisah sejarah awal penubuhan sekolah ini. Hasil dari usaha dan kesungguhan kami akhirnya dapat bertemu 4 pelajar terawal, tapi malangnya 3 orang daripada pelajar tersebut sudah tidak berupaya untuk menyingkap kembali detik sejarah ini disebabkan faktor usia. Hanya seorang yang sebaya usia dengannya berjaya diwawancara untuk menyingkap kembali detik bersejarah ini. Beliau dengan begitu bersemangat dan terharu menceritakan dari peringkat awal penubuhan sekolah ini untuk dijadikan kenangan kita bersama. Beliau yang dimaksudkan adalah Tuan Haji Kamaruddin Bin Ali , yang dilahirkan pada tanggal 24 April 1924 dan kini berusia 84 tahun . Beliau merupakan seorang pesara Guru Besar dan adalah anak kelahiran Kampung Gadong yang berkelulusan Malay College Kuala Kangsar (MCKK).  Untuk menyingkap kembali kisah sejarah sekolah ini, beliau dengan nada yang sebak mengingatkan peristiwa dan sejarah sewaktu mula memasuki alam persekolahan pada tanggal 1930 iaitu sebelum perang dunia ke-2, semasa Negara diperintah oleh British. 

         Bangunan kecil itu disekat untuk dijadikan 5 bilik darjah.  Sekolah ini tiada mempunyai kerusi dan meja. Berlantaikan papan di permukaan tanah, berdinding separuh tiang, dipakukan papan bersilang seli yang di panggil orang ( dinding berandar) beratap rumbia dan bumbung lentik konsep Minangkabau. Di bahagian belakang pula ada sedikit kawasan padang dan kebun sayur. Bayangkanlah……..  Dengan berbekalkan sebatang kalam dan sekeping papan batu berukuran kecil, beliau mula diajar guru menulis di atas lantai. Setelah penat duduk bersila, beralih meniarap dan ada juga yang mencangkung. Inilah kepayahan yang dialami ketika Negara ini diperintah oleh bangsa asing di mana tiada keistimewaan dan kemudahan seperti yang dinikmati oleh anak-anak kita pada zaman ini. Bersekolah memakai pakaian dari rumah, ada yang memakai kain sarung dan tidak kurang juga rakan-rakan yang berkaki ayam.  Di sekolah itu, terdapat 5 orang guru yang ditauliahkan untuk mengajar 100 orang murid. Mereka adalah En. Hassan b Pok ( Guru Besar ), En. Osman b Daud, Haji Mahmud, En. Samad, En. Md Dom b Hassan dan En. Abd hamid b Mahmud. Setelah tamat Perang Dunia ke-2 pada tahun 1950, sekolah ini dirobohkan dan diganti dengan bangunan yang baru. Sekolah ini diberi nama sekolah umum dan seterusnya pada tahun 1960 sekolah ini ditukar nama kepada Sekolah Kebangsaan Kota hinggalah sekarang.