SSB SAMKOT didirikan pada tahun 2004 oleh seorang mahasiswa IKIP PGRI Kaltim bernama Muhammad Saiin, yang dibantu oleh rekannya, Ari Suryanto. Awalnya, kegiatan ini berawal dari aktivitas ekstrakurikuler sepak bola di sekolah tempat mereka mengajar. Kebetulan, keduanya juga bekerja sebagai guru honorer pendidikan jasmani di beberapa sekolah negeri di Samarinda.
Seiring waktu, jumlah siswa yang ikut dalam kegiatan ini semakin bertambah. Menariknya, para siswa tidak hanya berasal dari sekolah tempat mereka mengajar, tapi juga dari berbagai sekolah lain dan berbagai jenjang usia. Melihat antusiasme yang tinggi, Muhammad Saiin kemudian berinisiatif untuk membentuk sebuah Sekolah Sepak Bola (SSB) khusus bagi anak-anak usia pelajar.
Karena lokasi latihan saat itu berada di sekitar Kota Samarinda, dan sebagian besar siswa berasal dari kota yang sama, maka dipilihlah nama Sekolah Sepak Bola Samarinda Kota, disingkat menjadi SSB SAMKOT. Untuk memperkuat tim pelatih, Muhammad Saiin mengajak rekan-rekannya dari kampus seperti Abdul Munawir dan Isriyadi untuk bergabung dalam kepelatihan.
Namun, setelah berjalan beberapa bulan, para pengurus merasa ada yang kurang. Anak-anak didik SSB SAMKOT belum mendapatkan kesempatan mengikuti kompetisi atau kejuaraan, baik tingkat kota, provinsi, hingga nasional seperti Piala Suratin, Danone Cup, maupun turnamen usia dini lainnya.
Setelah mencari informasi, ditemukan bahwa pada saat itu sangat sedikit kompetisi sepak bola antar pelajar di Kota Samarinda. Untuk itu, pengurus SSB SAMKOT, Muhammad Saiin dan Ari Suryanto, memutuskan untuk bersilaturahmi ke kantor PSSI Kota Samarinda dengan tujuan mendaftarkan SSB SAMKOT sebagai anggota resmi agar bisa mengikuti kompetisi.
Ternyata, pada waktu itu hanya ada satu SSB yang terdaftar di PSSI Kota Samarinda, yaitu SSB Persisam. Pihak PSSI menjelaskan bahwa untuk menjadi anggota resmi, SSB SAMKOT harus melengkapi sejumlah persyaratan seperti AD/ART, struktur kepengurusan, logo klub, akta notaris, dan dokumen pendukung lainnya.
Dengan semangat dan kegigihan, satu per satu persyaratan tersebut berhasil dipenuhi. Bahkan, pengurus berinisiatif untuk mengajukan Wali Kota Samarinda saat itu, Bapak Achmad Amins, sebagai penasehat klub. Mereka menyampaikan langsung maksud tersebut dengan bersilaturahmi ke rumah dinas beliau.
Tanpa disangka, Bapak Achmad Amins memberikan dukungan penuh terhadap inisiatif ini. Beliau berharap keberadaan SSB-SSB seperti SAMKOT dapat mendorong lahirnya kompetisi usia dini yang rutin dan memunculkan bibit-bibit atlet sepak bola dari Kota Samarinda.
Tak lama setelah itu, SSB SAMKOT resmi menjadi anggota PSSI Kota Samarinda. Keberhasilan ini pun mendorong terbentuknya SSB-SSB lain di pelosok Kota Samarinda, dan akhirnya kompetisi sepak bola usia dini yang diimpikan pun mulai terlaksana.