Two new species of pygmy goby of the Indo-Pacific genus Trimma are described. They are members of the erdmanni-chledophilum species group, which, according to recent genetic studies, is composed of diverse haplogroups representing several undescribed species. Trimma pamae, n. sp. is described from 6 specimens, 19.9–21.3 mm SL, collected from two sites in eastern Papua New Guinea. Diagnostic features include 9 segmented dorsal and 8 anal-fin rays; the second dorsal-fin spine long and filamentous; each segmented pelvic-fin ray with a single dichotomous branch point, the fifth ray 45–67% length of the fourth ray; the predorsal midline, cheek, and opercle scaleless; and the color in life mainly orange-red with distinctive blue stripes on the head behind the eye and on the midline of the snout. Trimma tufiensis n. sp. is described from two specimens, 19.3 and 19.9 mm SL, collected in the vicinity of Tufi, Oro Province, Papua New Guinea . It has similar diagnostic features as T. pamae, but lacks the blue stripes. Comparisons of mtDNA barcode sequences reveal the two new species are distinct lineages within the monophyletic group, with T. pamae 7.5% divergent from the nearest congener and T. tufiensis 3.8% from its sister species Trimma chledophilum.