Lethrinus miniatus and Lutjanus sebae are important commercial and recreational species of reef fish. Within Australian waters the former species is less widespread than the latter and has a discontinuous distribution, whilst the latter is continuously distributed in tropical Australian waters. The demographic attributes of these species (e.g. long life span, low rates of natural mortality) make them vulnerable to over-exploitation. Consequently, conservative harvest strategies including no-take zones for these species have been adopted by fisheries management agencies to control exploitation. Information on the genetic stock structure of these species is important for developing specific management strategies. However, little is known about genetic stock structures within and between east and west Australian populations of these species. The current study used the mitochondrial genome hypervariable region 1 (HVR1) of the control region to examine variation between two sites from both the east and west Australian coasts for each species. HVR1 for L. sebae did not differ genetically either within or between coasts (Fst < 0.018, p > 0.15) at the sites studied, suggesting a panmictic population structure. Similarly, L. miniatus did not differ significantly between sites sampled within coast. However, the west coast HVR1 for L. miniatus east and west coast populations, were discrete (Fst of at least 0.92, p < 0.0001). The degree of genetic sub-division between east and west coast populations indicates that they should be managed as discrete stocks. Further, when considering both species, the lower genetic (both haplotype and nucleotide) diversity in three of the four sites on the west coast of Australia, indicates that this region is genetically impoverished and neutrality tests suggest that selection is responsible. Consequently, west Australian populations will be less resilient to perturbations (e.g. fishing, climate change) than east Australian populations, which have higher genetic diversity.