The first traces of civilization in Bileća date from the Neolithic period, although archaeological sites are insufficiently explored. The first written documentation of Bileća as an inhabited place can be found in Ragusan documents dating from 1286, when it is mentioned under the name Bilechia. Bileća is mentioned in the 14th and 15th century as an important cross road town in caravan routes. A document dated 8 September 1388, mentions that the army of duke Vlatko Vuković defeated the Turkish army at the Battle of Bileća. In the period from 13th to 16th century in the history of this area is a large number of the "stećci" monolith markers which weigh up to 5 tons. Bileća was held by the Turks from 1466, although this was a rebellious area difficult to control. Nearby lies the town of Vučji Do, in which the Battle of Vučji Do took place in 1876. The Berlin's Congress included Bileća in the Austro-Hungarian Empire, which brought economic development to the region. The first primary school in Bileća was opened in 1880.
According to the 1910 census, the absolute majority in the Bileća municipality were Orthodox Christians (82.27%). According to the Kingdom of Yugoslavia 1931 population census, the majority was held by Orthodox Christians81.27%.