Cyanobacteria and eukaryotic algae are important primary producers in a variety of environments, yet their distribution and response to environmental change in saline lakes are poorly understood. In this study, the community structure of cyanobacteria and eukaryotic algae in the water and surface sediments of six lakes and one river on the Qinghai-Tibetan Plateau were investigated with the 23S rRNA gene pyrosequencing approach. Our results showed that salinity was the major factor controlling the community composition in these aquatic water bodies and the algal community structures of water and surface sediment samples grouped according to salinity. In subsaline-mesosaline lakes (salinity: 0.5-50 g L−1), Cyanobacteria (Cyanobium, Synechococcus) were highly abundant, while in hypersaline lakes (salinity: >50 g L−1) eukaryotic algae including Chlorophyta (Chlorella, Dunaliella), Bacillariophyta (Fistulifera), Streptophyta (Chara), and Dinophyceae (Kryptoperidinium foliaceum) were the major members of the community. The relative abundance ratio of cyanobacteria to eukaryotic algae was significantly correlated with salinity. The algae detected in Qinghai-Tibetan lakes exhibited a broader salinity range than previously known, which may be a result of a gradual adaptation to the slow evolution of these lakes. In addition, the algal community structure was similar between water and surface sediment of the same lake, suggesting that sediment algal community was derived from water column.