Soil degradation in Brazil is a concern due to intensive agricultural production. Combining conservation practice, such as no-tillage, with winter cover crops may increase microbial activity and enhance soil quality more than either practice alone. This research evaluated the benefits of long-term (23 years) winter cover crops and reduced tillage on soil microbial quality indicators in an Oxisol from Paraná State, Southern Brazil. The winter cover treatments were: fallow, black oat, wheat, radish, blue lupin, and hairy vetch in conventional (plow) or no-tillage management; the summer crop was a soybean/maize rotation. Soil quality parameters included organic C, microbial biomass C and N, total and labile polysaccharide, easily extractable and total glomalin-related soil protein, and enzyme activity. Winter crops increased soil microbial quality parameters compared to fallow in both tillage systems, with greater relative increase in conventional than no-tillage. No-tillage had higher microbial biomass, polysaccharide, glomalin-related soil protein, and soil enzyme activity than conventional tillage. Including legumes in the crop rotation was important for N balance in the soil–plant system, increasing soil organic C content, and enhancing soil quality parameters to a greater extent than grasses or radish. The microbial parameters proved to be more sensitive indicators of soil change than soil organic C. Cultivating winter cover crop with either tillage is a beneficial practice enhancing soil microbial quality and also soil organic C stocks.