Endemic to the Namib Desert, Fairy Circles (FCs) are vegetation-free circular patterns surrounded and delineated by grass species. Since first reported the 1970's, many theories have been proposed to explain their appearance, but none provide a fully satisfactory explanation of their origin(s) and/or causative agent(s). In this study, we have evaluated an early hypothesis stating that edaphic microorganisms could be involved in their formation and/or maintenance. Surface soils (0-5cm) from three different zones (FC center, FC margin and external, grass-covered soils) of five independent FCs were collected in April 2013 in the Namib Desert gravel plains. T-RFLP fingerprinting of the bacterial (16S rRNA gene) and fungal (ITS region) communities, in parallel with two-way crossed ANOSIM, showed that FC communities were significantly different to those of external control vegetated soil and that each FC was also characterized by significantly different communities. Intra-FC communities (margin and centre) presented higher variability than the controls. Together, these results provide clear evidence that edaphic microorganisms are involved in the Namib Desert FC phenomenon. However, we are, as yet, unable to confirm whether bacteria and/or fungi communities are responsible for the appearance and development of FCs or are a general consequence of the presence of the grass-free circles.