Continuous intensive monocultures of rice can lead to subsoil compaction, reduced topsoil quality and decline in rice yield. The objectives of this study were to evaluate the effect of rotating rice with upland crops on properties of an alluvial paddy clay soil, rice yield components, and economic profitability. A field experiment was established in the Vietnamese Mekong Delta for 10 years with a randomized complete block design including four rice based crop rotations and four replications: (i) rice–rice–rice (control, i.e., farmers’ practice), (ii) rice–maize–rice, (iii) rice–mung bean–rice, and (iv) rice–mung bean–maize. Rice alternated with upland crops significantly improved physical quality of soil in terms of bulk density, soil porosity, soil aggregate stability, and soil penetration resistance compared to the traditional rice monoculture practice, especially in the 10–20 and 20–30 cm depth layers. As a consequence, also rice rooting depth and root mass density was strongly increased in all three rice upland crop rotations. This resulted in a higher plant height, total number of tillers and panicles, filled grain percentage and a rice yield that was 32–36% higher compared to the control, and farmer’s profitability even increased 2.5–2.9 times. The reason for improved rice growth upon deeper root development should be investigated further, with specific attention to micronutrient availability.