The ‘maccullochi species group’ of rainbowfishes are small and distinctly patterned freshwater fishes of streams and swamps, comprising around eight species. The species from which the group bears its name, Melanotaenia maccullochi Ogilby, 1915, has been thought to comprise three forms occurring in distinct geographic areas, and recent mitochondrial genetic data provides matching patterns of likely inter-specific divergence. Here we undertake a detailed investigation of the taxonomic status of M. maccullochi using a combined lines of evidence approach incorporating multiple nuclear genetic markers (55 allozyme loci), mitochondrial DNA sequence data (1141 bp cytochrome b) and morphology (examination of a suite of 38 morphometric and meristic characters). As all three datasets provide support for a three-way split, we accordingly describe two new species and redescribe M. maccullochi sensu stricto. McCulloch’s Rainbowfish M. maccullochi, a species with brown body stripes and red fins occurs in northeast Queensland and is redescribed based on 338 specimens, 13.1–53.0 mm SL. This species was one of the first rainbowfishes to become known in the aquarium hobby. A second form with darker stripes on a contrasting light white-grey body and with distinct sub-marginal black bands in the dorsal and anal fins, distributed across northern and eastern Cape York Peninsula, Torres Strait and southern central New Guinea, is described as Sahul Rainbowfish M. sahulensis sp. nov. based on 267 specimens, 13.4–48.4 mm SL. A diminutive and well geographically isolated form occurring below the escarpment of the Tabletop Range in Litchfield National Park, Northern Territory possessing a more prominent and purplish mid-lateral stripe, is described as the Little Rainbowfish Melanotaenia wilsoni sp. nov. based on 50 specimens, 19.3–33.3 mm SL. A combination of morphological characters is useful for separating the respective taxa with M. wilsoni sp. nov. the most distinctive, typically having fewer vertebrae, lateral scales, cheek scales, procurrent caudal rays and anal rays and proportionally a shorter maxilla and snout than either of the other two species. Useful characters for further separating M. sahulensis sp. nov. from M. maccullochi include slightly higher counts of vertebrae, lateral scales and anal rays and proportionally greater body depth, body width and pre-dorsal distance. Information on the known distribution, habitats and conservation status of the three species is summarised, with the Northern Territory species being a narrow-range endemic with specific environmental requirements.