Born in the village of Trylies [be], then part of the Stoŭbtsy Raion within the Minsk Region of the Soviet Union's Byelorussian Soviet Socialist Republic, Lebedko emerged in the 1990s as one of the leading critics of Belarusian President Alexander Lukashenko, whom Lebedko, along with other opposition leaders and many western governments, considers a dictator.

Lebedko's strident opposition to Lukashenka led to increasingly bitter confrontations with the Belarusian authorities through the late 1990s and into the 2000s.

In particular, one of Lebedko's arrests came shortly after he had spoken on the floor of the United States Senate and at a meeting of the Organization for Security and Cooperation in Europe (OSCE) in October 1999, prompting letters of protest from both bodies.

Lebedko's supporters claim he was severely beaten by riot police following his arrest; he ended up in the hospital, reportedly with fractured skull, broken ribs and internal injuries.

At the Congress of Democratic Forces in October 2005, he lost by just a few votes to Alaksandar Milinkievič, who became (with Lebedko's subsequent support) the opposition's primary candidate in the 2006 Belarusian presidential election.