Lake Van is the largest saline soda lake in the world and one of the world’s few endorheic lakes of greater than 3,000 km2 surface area. Despite its huge size, no fish species have so far been known to permanently occur in this lake due to its extreme environmental conditions. Here, we report the discovery of a fish population that permanently inhabits some of the unique microbialites of the lake, at a maximum depth of 13 m and about 500 m offshore. We tested whether this is an undescribed species or a new occurrence of a known species. A molecular and morphological examination showed that the newly discovered fish represents an isolated population of Oxynoemacheilus ercisianus, the only nemacheilid loach native to the freshwater tributaries of the Lake Van endorheic basin. Our further hypotheses on the prediction that (a) stream fishes would have a more anterior placement of fins than lake fishes were supported; but, that (b) stream fishes would be more slender bodied than their lake conspecifics was not supported. The lake dwelling population also shows very small sequence divergence (0.5% K2P distance) to its stream dwelling conspecific in the mtDNA-COI barcode region. The notable morphological difference with minute molecular divergence implies that the newly discovered population might have lost its link to freshwater during desiccation and transgressional phases of the Lake Van, and has adapted to a life on the microbialites.