The KwaZulu-Natal yellowfish (Labeobarbus natalensis) is an abundant cyprinid, endemic to KwaZulu-Natal Province, South Africa. In this study we developed a Single Nucleotide Polymorphism (SNP) dataset from double-digest Restriction-site Associated DNA (ddRAD) sequencing of samples across the distribution. We addressed several hidden challenges, primarily focussing on proper filtering of RAD data and selecting optimal parameters for data processing in polyploid lineages. We used the resulting high-quality SNP dataset to investigate the population genetic structure of L. natalensis. A small number of mitochondrial markers present in these data had disproportionate influence on the recovered genetic structure. The presence of singleton SNPs also confounded genetic structure. We found a well-supported division into northern and southern lineages, with further subdivision into five populations, one of which reflects north-south admixture. Approximate Bayesian Computation scenario testing supported a scenario where an ancestral population diverged into northern and southern lineages, which then diverged to yield the current five populations. All river systems showed similar levels of genetic diversity, which appears unrelated to drainage system size. Nucleotide diversity was highest in the smallest river system, the Mbokodweni, which, together with adjacent small coastal systems, should be considered as a key catchment for conservation.