Degraded soil structure recovery is much less documented than structure degradation and in particular compaction. In this field experiment, the effects of rotary spade tillage followed by Sorghum cover crop (cover-crop treatment) on the degraded structure of the soil from an orchard were evaluated on undisturbed soil samples collected at 5–10 cm and 20–25 cm depth, respectively, using CoreVESS visual scoring of structure quality and shrinkage analysis. The cover-crop treatment took place from April to September and despite a particularly dry climate, the development of Sorghum was good. A large and significant improvement of the structure quality scores were obtained at both depths. Similar recovery trends in the physical properties were observed at the two depths, however the changes were significant at 5–10 cm depth only and were associated with a small increase of soil organic carbon (SOC) content. Analysis of covariance revealed a significant impact of the tillage and root development on the structure recovery, larger than the effect of SOC content. The structure recovery showed an increase of the positive role of SOC content on the physical properties. This structural change pattern was similar to those reported from other structure degradation or compaction studies. The slopes of the relationship between physical properties and SOC is an indicator of structure quality in general. Though the observed final structure quality of the top layer was good, we assume that its vulnerability remains large due to its small SOC to clay ratio. Our results are in close agreement with previous studies highlighting the relationships between SOC to clay ratio and structure quality.