The calcified encrusting brown-algal genus Newhousia was collected in 2012 from two sites in Madang Lagoon, northern Papua New Guinea. This is the first report of that enigmatic genus since its original description in 2004 from Oahu in the Hawaiian Islands. Morphologies of thalli from both Papuan localities agree with the original diagnosis and the published figures of the Hawaiian Newhousia imbricata. Ribulose-1, -5-biphosphate carboxylase large subunit (rbcL) sequences of Papuan specimens were 96% identical to those of N. imbricata, and although there were no outstanding morphological differences between the Hawaiian and the Papuan specimens, the genetic divergence between the two strongly indicates they are not conspecific. A formal description of the new species, Newhousia yhaga, is provided and the phylogenetic implications of concatenated cox3, psbA and rbcL sequences evaluated. A multimarker phylogeny was generated in the hope to establish the precise phylogenetic position of Newhousia within the order Dictyotales. Even though both Bayesian inference (BI) and maximum likelihood (ML) analysis point to Newhousia being sister to Lobophora, these results are not supported by ML bootstrap values. The present documentation of Newhousia in a southwest Pacific locality considerably extends the geographical range of this unusual genus.