Two new species of Chrysomelobia Regenfuss, 1968, C. alleni n. sp. and C. intrusus n. sp., are described from Tasmanian specimens of the eucalyptus leaf beetle Paropsis charybdis Stål. This beetle is now known to host three species of Chrysomelobia, the other being Chrysomelobia pagurus Seeman, 2008, which is recorded from Tasmania for the first time. Thus, the three species of Paropsis Olivier known to have podapolipid mites each have three mite species from three separate lineages of Chrysomelobia. Collections of P. charybdis in New Zealand (n = 150), where it is an invasive pest species, failed to locate any infested beetles, suggesting that these populations were established by uninfested beetles. The prospect of using these mites as biocontrol agents is discussed.