Two new species of the genus Lepidapedoides are described from the aulopodid teleost Aulopus purpurissatus from south-western Australia. Both are distinguished from other Lepidapedoides spp. by their pedunculate ventral sucker. Lepidapedoides pistoris n. sp. and L. elongatrium n. sp. are distinguished by the possession of a narrow, elongate form, a long ventral sucker to ovary distance, the vitellarium reaching only to the posterior level of the cirrus-sac, the cirrus-sac length and the deep genital atrium with the metraterm entering distally to its base in L. elongatrium. A key to species of the genus is given. A character matrix is included for the genus. Poorly resolved phylogenetic trees indicate two main lineages in the genus. The two new species described here are resolved as sister taxa. The new combination Lepidapedoides freitasi (Kohn & Fernandes, 1970) is formed for Acanthocolpoides freitasi.