The Kalahari of southern Africa is characterised by sparse vegetation interspersed with microbe-dominated biological soil crusts (BSC) which deliver a range of ecosystem services including soil stabilisation and carbon fixation. We characterised the bacterial communities of BSCs (0–1 cm depth) and the subsurface soil (1–2 cm depth) in an area typical of lightly grazed Kalahari rangelands, composed of grasses, shrubs, and trees. Our data add substantially to the limited amount of existing knowledge concerning BSC microbial community structure, by providing the first bacterial community analyses of both BSCs and subsurface soils of the Kalahari region based on a high throughput 16S ribosomal RNA gene sequencing approach. BSC bacterial communities were distinct with respect to vegetation type and soil depth, and varied in relation to soil carbon, nitrogen, and surface temperature. Cyanobacteria were predominant in the grass interspaces at the soil surface (0–1 cm) but rare in subsurface soils (1–2 cm depth) and under the shrubs and trees. Bacteroidetes were significantly more abundant in surface soils of all areas even in the absence of a consolidated crust, whilst subsurface soils yielded more sequences affiliated to Acidobacteria, Actinobacteria, Chloroflexi, and Firmicutes. The common detection of vertical stratification, even in disturbed sites, suggests a strong potential for BSC recovery after physical disruption, however severe depletion of Cyanobacteria near trees and shrubs may limit the potential for natural BSC regeneration in heavily shrub-encroached areas. ; The original publication is available at www.springerlink.com