Paddy and upland soils in the southern regions of China are commonly contaminated by a complex of cadmium (Cd) and arsenic (As), which severely affects soil quality and crop growth. Therefore, studying the bioavailability of Cd and As and their influencing factors is of great environmental and agricultural significance. In this study, 18 pairs of paddy and neighboring upland soils developed from purple sandstone, gravel, limestone, slate shale, and quaternary laterite were compared to analyze differences in the availability of Cd and As, key physicochemical properties, and dominant microbial taxa. The results showed that the availability of Cd and As in paddy soils was significantly correlated with the total soil Cd and As content (r = 0.74, r = 0.78; P < 0.01). In contrast, the availability of Cd and As in upland soils was significantly correlated with soil pH, total As, and total phosphorus content (r = 0.45, r = 0.61, r = -0.55; P < 0.05). Analysis of the microbial community structure at the phylum level revealed that the microbial taxa in paddy soils with different parent materials were similar, with associations to processes such as nitrite oxidation, iron reduction, and nitrogen fixation. On the other hand, microbial communities in upland soils derived from slate shale, limestone, and quaternary laterite were mainly associated with iron reduction and sulfur oxidation processes. Regression analysis indicated that the primary microorganisms influencing the bioavailability of Cd and As in paddy soils were sulfur-oxidizing bacteria (e.g., Sulfopaludibacter) and iron-reducing bacteria (e.g., Pedosphaera), while in upland soils, denitrifying bacteria (e.g., Steroidobacter) and anaerobic slime molds (e.g., Anaeromyxobacter) were the key drivers. Redundancy analysis (RDA) revealed that soil pH, total As, active Fe, and active sulfur content were key environmental factors influencing the relative abundance and functions of dominant microbial taxa. In summary, regulating the key physicochemical properties of soils and the relative abundance and functions of dominant microorganisms involved in nitrogen, iron, and sulfur cycles can provide a theoretical foundation for reducing the bioavailability of Cd and As in both paddy and upland soils. This approach can also serve as an important reference for the remediation of Cd and As co-contaminated soils in southern China.