Microcystis aeruginosa is a bloom-forming cyanobacterium found in eutrophic water bodies worldwide. M. aeruginosa blooms usually occur in freshwater; however, they have also been reported to occur in brackish water. Because M. aeruginosa often produces the cyanotoxin microcystin, they are a major concern to public health and environment. Despite this, the ecology, genomic basis, and evolutionary process underlying the M. aeruginosa bloom invasion from fresh to brackish water have been poorly investigated. Hence, in the present study, we have sequenced and characterized genomes of two newly discovered salt-tolerant M. aeruginosa strains obtained from Japanese brackish water lakes (Lakes Shinji and Tofutsu). Both genomes contain a set of genes for the synthesis of osmolyte sucrose (sppA, spsA, and susA), hitherto identified in only one strain (PCC 7806) of M. aeruginosa. Chemical and gene expression analyses confirmed sucrose accumulation induced by salt. A comprehensive genetic survey of >200 strains indicated that sucrose genes are extremely rare in M. aeruginosa. Most surprisingly, comparative genome analyses of the three strains indicated extremely low genetic diversity in the sucrose genes compared with other core genome genes, suggesting very recent acquisitions via horizontal transfer. Invasion of M. aeruginosa blooms into brackish water may be a recent event triggered by anthropogenic eutrophication of brackish water.