The assassin bugs of the genus Ptilocerus Gray, 1831 (Hemiptera: Heteroptera: Reduviidae: Holoptilinae) occurring in the Australian Region are reviewed for the first time, resulting in the description of two new species, viz., P. spangenbergi sp. nov. (Queensland and Northern Territory, Australia) and P. papuensis sp. nov. (Papua New Guinea). The latter species differs from P. fuscus Gray, 1831 (the type-species of genus Ptilocerus) in a couple of major external morphological characters, hence its tentative placement in the genus Ptilocerus is discussed. A key for the separation of the two new species is provided.