A new genus and species of deep-sea shrimp, Maximiliaeus odoceros, was collected from the Solomon Sea off Papua New Guinea. This penaeoid has a characteristic carapace: bearing large teeth on its entire dorsal border, and the presence of three parallel carinae that nearly run the entire length of the lateral carapace surface. Phylogenetic analysis using PEPCK and NaK sequences confirmed that this new taxon belongs to Solenoceridae.