Soil structural stability is a vital aspect of soil quality and functions, and of maintaining sustainable land management. The objective of this study was to compare the contribution of four long-term land-use systems (crop, bush, grass, and forest) coupled with anionic polyacrylamide (PAM = 0, 25, and 200 mg L−1) application on the structural stability of soils in three watersheds of Ethiopia varying in elevation. Effect of treatments on soil structural stability indices were assessed using the high energy moisture characteristic (HEMC, 0–50 hPa) method, which provides (i) water retention model parameters α and n, and (ii) soil structure index (SI). Soil (watershed), land use and PAM treatments had significant effects on the shape of the water retention curves (α, n) and SI, with diverse changes in the macropore sizes (60–250; >250 μm). Soil organic carbon (SOC) content and SI were strongly related to soil pH, CaCO3 soil type-clay mineralogy, exchangeable Ca2+, and Na+ (negatively). The order of soil SI (0.013–0.064 hPa−1) and SOC (1.4–8.1%) by land use was similar (forest > grass > bush > cropland). PAM effect on increasing soil SI (1.2–2.0 times), was inversely related to SOC content, being also pronounced in soils from watersheds of low (Vertisol) and medium (Luvisol) elevation, and the cropland soil from high (Acrisol) elevation. Treating cropland soils with a high PAM rate yielded greater SI (0.028–0.042 hPa−1) than untreated bush- and grassland soils (0.021–0.033 hPa−1). For sustainable management and faster improvement in soil physical quality, soil properties, and land-use history should be considered together with PAM application.