The town was founded in the 19th century as the settlement Yermolovsk (Russian: Ермоловск), named in honor of the Minister of Agriculture A.S. Yermolov who traveled to this place in 1894.

Some authors linked the name of the settlement to General Yermolov (commander of the Caucasian war), but this presumption is apparently erroneous.

[4] In 1944 the town was officially renamed in honor of the national hero Colonel-General Konstantin Leselidze (1903-1944) who fought in the Caucasus during World War II.

In autumn of 1993 in the vicinity of Gagra and the town Lеselidze 'the commander' personally led a punitive action for the extermination of refugees.

According to the accounts of miraculously survived eyewitnesses, the bandits took pleasure in videotaping the scenes of abuse and rape.” Under Abkhazian control the town is known to feature two all-inclusive resorts - "Gech" and "Laguna".