Coal and lignite play a major energy supply role in many European countries, including Bosnia and Herzegovina. Yet mining activities are a heavy source of ecosystem contamination, posing significant environmental threats. The primary goal of this study was to isolate and identify autochthonous lignite mine spoil bacteria and evaluate their potential in bioremediation of these polluted soils. Two Bacillus species, Bacillus simplex and a Bacillus cereus group member, were identified using conventional, molecular, and bioinformatics approaches. This represents, to our knowledge, the first microbial characterization of mine overburden in Bosnia and Herzegovina. A co-inoculum of autochthonous bacterial populations was used to treat unvegetated as well as oat- and lettuce-vegetated lignite overburden samples. Our results illustrate the potential of recovered native species to enrich soil fertility and productivity through plant growth promotion.