The small fishes of the gobiid genus Tryssogobius Larson & Hoese, 2001 are represented by the following five species: T. colini Larson & Hoese, 2001 from Indonesia, Malaysia, and Papua New Guinea in 27-41 m; T. flavolineatus n. sp. from New Guinea and Indonesia in 28-82 m; T. longipes Larson & Hoese, 2001 from Indonesia and Papua New Guinea in 19.5-27 m; T. nigrolineatus n. sp. from Fiji from 73-110 m; and T. quinquespinus n. sp. from Papua New Guinea in 27 m. They are distinguished primarily by fin-ray counts and in colour.