Paedogobius kimurai, a new genus and species of Gobiidae, is described. This diandric genus is unique among the Gobiidae in having a long rod-shaped pelvis separated posteriorly into distinct left and right halves and no subpelvic process; and the ectopterygoid and quadrate widely separated in the secondary male. This genus is also distinguishable from the other genera of Gobiidae in having the following combination of characters: a maxillo-vomerine meniscus; the posteriormost soft dorsaland anal-fin pterygiophores each supporting an unbranched soft ray; 10 abdominal and 15 caudal vertebrae; the first one or two dorsal-fin pterygiophores inserting between the 9th and 10th neural spines; some sensory papillae on the branchiostegal region; and no first dorsal fin. Mature females (about 15 mm SL) have a transparent body with only a few melanophores, no pelvic fins, small jaws with a few minute teeth, and the nostrils formed into a single pit. Secondary males (about 16 mm SL) have pelvic fins, many melanophores especially on the head, and a robust head with large jaws armed with long canine-like teeth, and two nostrils. Primary males (about 12 mm SL), are smaller than females, and also have pelvic fins and two nostrils; however, the head is not robust, the small jaws are armed with a pair of short canine-like teeth and pigmentation is diffuse. This species is known from Japan, Thailand and northeastern Australia.