We describe two new species of Parosphromenus from Indonesia based on morphological and molecular diagnoses. Parosphromenus juelinae, sp. nov., occurs on Bangka Island. Its unpaired fin coloration is similar to that of P. deissneri, but it differs from the latter in having a rounded caudal fin with a non-filamentous branched median ray and a smaller anal fin. Although the new species has the same caudal fin structure as P. bintan, it can be distinguished from the latter by its distinct unpaired fin coloration and the intense red color on the body flanks. Parosphromenus kishii, sp. nov., is found only in a single river system in Kalimantan Tengah. It is distinguished from all other congeners by the unique coloration of its caudal fin. A phylogenetic tree based on the cytochrome b (cytb) gene indicates that the two new species are distinct monophyletic groups constituting distinct phylogenetic branches from their congeners. Cytochrome b Genetic distances between Parosphromenus juelinae, sp. nov., and Parosphromenus kishii, sp. nov., and the other taxa in the phylogenetic tree range from 2.44% to 19.52% and from 8.65% to 17.28%, respectively.