Recessive dystrophic epidermolysis bullosa is characterized by skin blistering and wounds. To uncover the changes in the skin and mucosal microbiome related to age and disease progression and microbiome impact on clinical and inflammatory laboratory parameters, swabs from wounded and unwounded skin, oral mucosa, and stool samples of 28 children with recessive dystrophic epidermolysis bullosa and 28 healthy controls were subjected to 16S-ribosomal RNA gene sequencing. Skin microbiome of patients with recessive dystrophic epidermolysis bullosa showed significantly reduced alpha diversity compared with that of healthy controls and showed significantly early, age-dependent predominance of Staphylococcus aureus, first in wounded skin and then in unwounded skin. These findings were more pronounced in the severe disease with higher abundances of S. aureus than in intermediate disease. S. aureus abundance correlated significantly with both acute and chronic wound burden. Changes in oral mucosal and gut microbiome were discrete, with no significant differences in alpha diversity. Our findings show that children with recessive dystrophic epidermolysis bullosa experience skin microbiome changes early in life. Longitudinal studies should confirm that dysbiosis starts in wounds and later extends to unwounded skin. The predominance of S. aureus significantly correlates with wound burden and disease activity and, to some extent, with systemic inflammation.