We present one of the first studies of DNA barcodes (COI sequences) in the basal insect order Zygentoma, and compare the data with nuclear (28S) and mitochondrial (16S) rDNA sequences and morphology for an integrative taxonomic study of the Heterolepisma sclerophylla Smith species group. DNA sequence analyses identified deep divisions between Queensland and New South Wales populations, and among populations in each state. Detailed morphological and morphometric evaluation of the specimens failed, in most cases, to identify unambiguous morphological characters of diagnostic value for each population, possibly due to the interaction of morphological conservatism with high levels of variability resulting from their continued moulting after reaching sexual maturity. Several strong consistent characters were identified to support the description of a southern Queensland population as a new species (Heterolepisma cooloola sp. nov.). The combined molecular and morphological data support the view that the presence of lanceolate scales and the absence of macrochaetae from the anterior margin of the frons are more significant to phylogeny than the arrangement of styli and the shape of the thoracic sternites in Heterolepisma. Specimens from Glen Davis, NSW, while indistinguishable from H. sclerophylla in all other characters examined, were found to possess one fewer pair of abdominal styli in both sexes and are also described as a new species (Heterolepisma coorongooba sp. nov.). Five lineages are recognized within the remaining NSW material but as reliable (non-overlapping) morphological and morphometric differences could not be identified, they are not described here as new species. Heterolepisma sclerophylla sensu stricto is considered to be a complex of morphologically ill-defined species or perhaps subspecies.