Two new species of Aphelodoris Bergh are described from the north-western coast of Australia. Aphelodoris gigas sp. nov. has been found only in the Dampier and Kimberley regions in Western Australia, while A. karpa sp. nov. is known to occur in northern Western Australia and also in the Northern Territory. These species both possess a two-part prostate; this is the first time this has been reported in the genus Aphelodoris, and thus lends support for inclusion in the family Halgerdidae. Redescription of A. greeni Burn from Tasmania indicates that a two part prostate also occurs in at least one southern Australian species. The range extension reported here for A. greeni indicates that it is sympatric with A. juliae Burn in southern Tasmania, and not allopatric as was previously thought. The sperm morphology of A. gigas sp. nov., A. greeni Burn and A. varia (Abraham) is described, and shows acrosomal internal structure (short, angular striations through part of the pedestal) that is to date unrecorded among the Doridina. The spermatological characteristics of these Aphelodoris species appear most similar to the dorid genera Sclerodoris and Asteronotus.