Land-use change due to the widespread practice of swidden agriculture affects the supply of ecosystem services. However, there is comparatively little understanding of how the hydrological functioning of soils, which affects rainfall infiltration and therefore flood risk, dry-season flows and surface erosion, is affected by repeated vegetation clearing and burning, the extent to which this can recover following land abandonment and vegetation regrowth, and whether active restoration speeds up recovery. We used interviews with local land users and indicator plant species to reconstruct the land-use history of 19 different sites in upland eastern Madagascar that represent four different land-use categories: semi-mature forests that were never burnt but were influenced by manual logging until 15–20 years ago; fallows that were actively reforested 6–9 years ago; 2–10 year old naturally regenerating fallows; and highly degraded fire-climax grassland sites. Surface- and near-surface (down to 30 cm depth) saturated soil hydraulic conductivities (Ksat), as well as the dominant flow pathways for infiltration and percolation were determined for each land-cover type. Surface Ksat in the forest sites was very high (median: 724 mm h−1) and infiltration was dominated by flow along roots and other preferential flow pathways (macropores), whereas Ksat in the degraded land was low (median: 45 mm h−1) with infiltration being dominated by near-surface matrix flow. The total area of blue-dye stains was inversely correlated to the Ksat. Both surface- and near-surface Ksat had increased significantly after 6–9 years of forest regeneration (median values of 203 and 161 mm h−1 for reforestation and natural regeneration, respectively). Additional observations are needed to more fully understand the rates at which soil hydrological functioning can be rebuilt and whether active replanting decreases the time required to restore soil hydrological functioning or not.