Four new species of Ceratomyxa Thélohan, 1892 are described from the gall bladders of fishes collected off Lizard Island, Australia. These species are characterised using a combination of morphometric and molecular data. Ceratomyxa bartholomewae sp. n. is described from Hyporhamphus dussumieri (Valenciennes) (family Hemirhamphidae); C. koieae sp. n. is described from Sphyraena forsteri Cuvier (family Sphyraenidae); C. pantherini sp. n. is described from Bothus pantherinus (Rüppell) (family Bothidae) and C. reidi sp. n. is described from Chaetodon vagabundus Linnaeus (family Chaetodontidae). A fifth species from Zebrasoma veliferum (Bloch) (family Acanthuridae) is also reported but due to limited material is not formally described here.