Shrub encroachment is occurring in many of the world’s drylands, but its impacts on ecosystem structure and function are still poorly understood. In particular, it remains unclear how shrub encroachment affects dryland soil surfaces, including biological soil crust (biocrust) communities. In this study, soil surfaces (0–1 cm depth) were sampled from areas of Grewia flava shrubs and Eragrostis lehmanniana and Schmidtia kalahariensis grasses in the southwest Kalahari during two different seasons (March and November). Our hypothesis is that the presence of different vegetation cover types (shrubs versus grasses) alters the microbial composition of soil surfaces owing to their contrasting microenvironments. The results showed that more significant differences in microclimate (light, soil surface temperatures) and soil surface microbial communities were observed between shrubs and grasses than between sampling seasons. Based on high-throughput 16S rRNA gene sequencing, our findings showed that approximately one third (33.5%) of the operational taxonomic units (OTUs) occurred exclusively in soil surfaces beneath shrubs. Soil surfaces with biocrusts in grass areas were dominated by the cyanobacteria Microcoleus steenstrupii, whereas the soil surfaces beneath shrubs were dominated by the proteobacteria Microvirga flocculans. Soil surfaces beneath shrubs are associated with reduced cyanobacterial abundance but have higher total carbon and total nitrogen contents compared to biocrusts in grass areas. These findings infer changes in the relative contributions from different sources of carbon and nitrogen (e.g. cyanobacterial and non-cyanobacterial fixation, plant litter, animal activity). The distinctive microbial composition and higher carbon and nitrogen contents in soil surfaces beneath shrubs may provide a positive feedback mechanism promoting shrub encroachment, which helps to explain why the phenomenon is commonly observed to be irreversible.