Sabah, also known as North Borneo, is one of the states in Malaysia. It is home to many local varieties of rice, but the self-sufficiency quotient for rice production is only about 30%. Knowledge of the genetic diversity of crops has been utilised to increase crop yields including rice in different countries, but the information regarding the genetic diversity of Sabah traditional rice varieties is very limited. Therefore, we report a comprehensive genetic diversity and relationship study of 22 Sabah traditional rice varieties in three main divisions of Sabah including the West Coast Division (WCD), Sandakan Division (SD), and Interior Division (ID) using 11 random amplified polymorphic DNA (RAPD) markers. Our results showed that more than half of the collected rice seeds were medium in size and shape, with moderately high head rice recovery and low moisture content. In addition, about half of them were categorised with high to very high amylose content. Genetic analysis revealed a total of 75 bands were produced using all RAPD markers with 100% polymorphism, and a high degree of genetic variation among all Sabah traditional rice varieties was obtained. The genetic differentiation of Sabah's traditional rice varieties was more likely to occur within divisions rather than among divisions. Furthermore, Sabah traditional rice varieties in ID showed the greatest genetic diversity and polymorphic loci, and were closely related to rice varieties in SD but genetically dissimilar to those in WCD as revealed in both phylogenetic tree and principal component analysis. In conclusion, this study provides breeders with reliable information regarding diversity of Sabah's traditional rice varieties; the data could also be beneficial for local rice yield enhancement.