Two new species of Cryptoxilos are described from the South Pacific region. A new species from Auckland, New Zealand, Cryptoxilos thorpei Shaw & Berry, is described and illustrated. This is the first described species of the genus Cryptoxilos from New Zealand. The species is associated with a scolytine bark beetle, Chaetoptelius mundulus (Broun) (Coleoptera : Scolytinae), on a dead Pittosporum tree. A second new species, Cryptoxilos beaveri Shaw & Berry, is described from Fiji, also a new locality record for the genus. The species is associated with cryphaline ambrosia beetles, Hypothenemus curtipennis and Hypothenemus dorsosignatus, in the tree Commersonia bartramia. The existing subgenus classification system is discussed in relation to character states expressed in these two new species. Neither new species can be easily assigned to a subgenus based on the existing system. Given serious problems in the consistent application of the previous subgenus system, we recommend that subgenera be abandoned and we treat subgenus Cryptoxiloides simply as a junior synonym of Cryptoxilos.