Pada tahun 1965, penduduk Kampung Kelatuan telah membina sebuah sekolah secara bergotong royong di atas sebidang tanah yang mempunyai keluasan kira-kira setengah hektar sahaja. Tanah tersebut diperolehi daripada Allahyarham Orang Tua Abdullah Bin Banawa. Selain daripada sekolah ini, terdapat dua buah sekolah di kampung ini. Sekolah tersebut ialah SRJK Our Lady Of Fatima (Aliran Bahasa Inggeris) dan SRJK Sin Ming (Aliran Bahasa Cina).Pada mulanya, sekolah ini hanya mempunyai sebuah bangunan. Manakala atapnya adalah daripada zink dan rumbia. Dindingnya pula adalah dripada papan dan sebahagiannya berdindingkan pelepah rumbia serta berlantaikan tanah liat. Kerusi dan meja telah diusahakan oleh ibubapa sendiri, di atas keprihatinan mereka terhadap pendidikan anak-anak di kampung tersebut. Setelah usia sekolah menjangkau 10 tahun (1975), Jabatan Pendidikan Sabah telah mengambil alih sepenuhnya pentadbiran sekolah ini. Sebuah bangunan baru yang dapat menampung dua buah bilik darjah, dua buah bilik stor dan sebuah rumah guru telah dibina. Projek tersebut telah menelan belanja sebanyak lebih kurang RM50 000.
Pada 30hb.Januari.1976, bangunan baru tersebut telah dirasmikan oleh YB Datuk Haji Dzulkifli Bin Datuk Haji Abdul Hamid, yang merupakan Menteri Kewangan Negeri Sabah pada ketika itu. Dengan perasmian itu, maka sekolah ini telah dinamakan sebagai "SEKOLAH KEBANGSAAN KELATUAN, PAPAR" dan menjadi Hak Milik Kerajaan sepenuhnya. Pada tahun 1982, Jabatan Pendidikan Sabah telah berusaha untuk memperbesarkan kawasan sekolah ini. Sebidang tanah dengan keluasan satu setengah hektar yang bersempadanan dengan kawasan sekolah telah dibeli oleh pihak Jabatan Pendidikan Sabah pada ketika itu. Dengan pembelian tanah tersebut, keluasan tanah sekolah telah menjadi 2 hektar.
Pada tahun 1984, Jabatan Pendidikan Sabah telah membina dua lagi unit bangunan tambahan untuk menampung pertambahan jumlah pelajar yang telah mencapai angka 178 orang murid. Projek tersebut telah dilaksanakan melalui Projek Bank Dunia yang bernilai RM250,000.00. Bangunan tersebut turut menampung dua buah rumah guru dan sebuah padang bola sepak. Pada tahun 1985, bangunan ini telah siap sepenuhnya. Pihak pentadbiran sekolah pada ketika itu telah memutuskan untuk merobohkan bangunan lama kerana keselamatannya tidak terjamin, selain kelihatan agak usang. Sebuah lagi bangunan serbaguna telah siap dibina pada tahun 1993 dengan perbelanjaan sebanyak RM20,000.00. Lebih kurang lima tahun kemudian, iaitu pada penghujung tahun 1998, sebuah kantin telah dibina oleh Jabatan Pendidikan Sabah. Hasil daripada kerjasama pihak sekolah, PIBG dan penduduk kampung, sebuah bangunan Bengkel Kemahiran Hidup turut dibina.
Pada hari ini, Sekolah Kebangsaan Kelatuan, Papar telah bertukar wajah. Sekolah ini telah memilik empat buah bangunan yang selesa serta dilengkapi bilik-bilik khas seperti Bilik Serbaguna, Bilik Pusat Sumber, Bilik Guru, Pejabat Guru Besar dan Pejabat Pentadbiran. Beberapa kemudahan lain juga turut disediakan termasuklah bekalan air paip, elektrik, telefon serta pondok-pondok pembelajaran.
