Settlement in the vicinity of Lebus has been traced as far back as 3,000 years. The ridges provided natural defense and led to fortifications being constructed upon them. The Germanic Lombards and Semnoni are believed to have lived in the area before the Common Era. Since approximately 7th century area inhabited by the Slavic tribe Leubuzzi, Lechitic tribe considered to be transitional between Poles and Liutici. The land on both sides of the Oder became known as Terra Lebusana ("land of the Leubuzzi" in Latin, Polish: Ziemia Lubuska).
The region was conquered and brought under Polish control by 966 under the rule of Duke Mieszko I. A castellan's castle was built to control it. It was Polish stronghold against German invasion, so the thirteenth-century chronicles named Lebus "the key to the Kingdom of Poland", which was a battleground for neighboring rulers. This Lubusz Land, which provides the name for the present-day Lubusz Voivodeship in Poland, was especially influenced by the Piast dukes in Silesia. Settlement was mentioned as a town Liubusua and Libusua urbs in the annals of Thietmari merseburgiensis episcopi chronicon written in the years 1012 - 1018 by the Bishop of Merseburg and chronicler Thietmar.
The Bishopric of Lubusz was founded in 1124-25 during the reign of Bolesław III Wrymouth to counter and convert the Liutizi. It served as an important center for Catholic missionaries preaching in and developing the Oder region. In 1163 Emperor Frederick I, Holy Roman Emperor granted the Lubusz Land on both sides of the Oder as a fief to the Silesian Piasts. German colonization of the region proceeded throughout the 13th century and the settlement became predominantly known as Lebus. Duke Henry I of Silesia granted it German town law in 1226. The Ascanian Margraviate of Brandenburg acquired the region ca. 1250.
During the Middle Ages, Lebus served as an important stop on trade routes from the Baltic Sea to Italy and from Poznań to Flanders. After the destruction of the town's cathedral by troops of Emperor Charles IV in 1373, the seat of the bishopric was moved from Lebus to Fürstenwalde. The populace became Lutheran during the Protestant Reformation, and the bishopric was secularized in 1555 following the death of the last Catholic bishop, Georg von Blumenthal. After the 16th century fires and political changes weakened the fortifications; the castle was decisively damaged by a lightning strike in 1713. Lebus gradually became a backwater locality.
During World War II, Lebus, including its medieval center, was almost completely destroyed. While Lebus remained part of East Germany, the area east of the Oder became part of Poland in 1945 according to the Potsdam Agreement. The parish church of Lebus was restored in 1954.
Since the last administrative reform of Poland, one of 16 Polish provinces has been named Lubusz Voivodeship or Province of Lebus.