Archaea and bacteria are important drivers for nutrient transformations in soils and catalyse the production and consumption of important greenhouse gases. In this study, we investigate changes in archaeal and bacterial communities of four Czech grassland soils affected by outdoor cattle husbandry. Two show short-term (3 years; STI) and long-term impact (17 years; LTI), one is regenerating from cattle impact (REG) and a control is unaffected by cattle (CON). Cattle manure (CMN), the source of allochthonous microbes, was collected from the same area. We used pyrosequencing of 16S rRNA genes to assess the composition of archaeal and bacterial communities in each soil type and CMN. Both short- and long- term cattle impact negatively altered archaeal and bacterial diversity, leading to increase of homogenization of microbial communities in overwintering soils over time. Moreover, strong shifts in the prokaryotic communities were observed in response to cattle overwintering, with the greatest impact on archaea. Oligotrophic and acidophilic microorganisms (e.g. Thaumarchaeota, Acidobacteria, and α-Proteobacteria) dominated in CON and expressed strong negative response to increased pH, total C and N. Whereas copiotrophic and alkalophilic microbes (e.g. methanogenic Euryarchaeota, Firmicutes, Chloroflexi, Actinobacteria, and Bacteroidetes) were common in LTI showing opposite trends. Crenarchaeota were also found in LTI, though their trophic interactions remain cryptic. Firmicutes, Bacteroidetes, Methanobacteriaceae, and Methanomicrobiaceae indicated the introduction and establishment of faecal microbes into the impacted soils, while Chloroflexi and Methanosarcinaceae suggested increased abundance of soil-borne microbes under altered environmental conditions. The observed changes in prokaryotic community composition may have driven corresponding changes in soil functioning.