Population genetic structure of migratory fishes can reflect ecological and evolutionary processes. Pangasius krempfi is a critically important anadromous catfish in the Mekong River, and its migration pathways and genetic structure have attracted much interest. To investigate, we quantified the genetic diversity of this species using the control region (D-loop) and Cytochrome b (Cytb) of the mitochondrial genome. Fish were sampled (n = 91) along the Mekong tributaries from upstream to estuaries and coastal areas in the Mekong Delta and compared to three samples from Pakse (Laos). The D-loop haplotype (0.941 ± 0.014) and nucleotide diversity (0.0083 ± 0.0005) were high in all populations, but that of Cytb was low (0.331 ± 0.059 and 0.00063 ± 0.00011, respectively). No genetic difference was detected between populations, indicating strong gene flow and confirming a long migration distance for this species. Pangasius krempfi was not genetically structured according to geographical populations but was delineated into three haplogroups, suggesting multiple genetic lineages. The presence of haplogroups in each sampling location implies that migration downstream is random but parallel when the fish enter two river tributaries bifurcating from the main Mekong River. Individuals can also migrate along the coast, far from the estuaries, suggesting a longer migration path than previously reported, which is crucial for maintaining diverse genetic origin and migration pathways for P. krempfi.