Urban land use and land cover (LULC) change profoundly alters natural surfaces, accelerates runoff, and increases flood risks. However, the coupling between land cover dynamics and urban hydrologic responses (LCDUHR), and its implications for nature-based mitigation, remains poorly understood in data-scarce regions. This study bridges this gap by integrating multi-temporal remote sensing, machine learning (ML), and hydrologic–hydraulic simulation (SWMM 5.2) to assess land-cover-driven hydrologic responses and evaluate sustainable flood mitigation options in Shahjalal Uposhahar, Sylhet, Bangladesh. Ten ML-based models analyzed satellite imagery (2003–2023) and projected LULC to 2033, outperforming conventional classification approaches. Results show that 26.70% of natural surfaces were converted to built-up areas between 2003 and 2023, increasing surface runoff by 11.89–26.97 mm across 2–100-year return periods. By 2033, imperviousness is projected to increase by an additional 2% (relative to 2023), accompanied by continued declines in water bodies and barren land, further exacerbating pluvial flooding. Twelve nature-based solutions (NbS) were modeled as sponge landscape interventions to assess flood mitigation potential. Bioretention ponds achieved the greatest reductions, with a 75% reduction in peak runoff, 27.11–30.15% in runoff volume, and 34.08–50.61% in total flooding, while rain gardens, infiltration trenches, and green roofs also performed effectively. Despite these improvements, existing drainage capacity remains insufficient under extreme storms. This study provides data-driven, spatially explicit insights for designing NbS-integrated urban drainage systems, supporting Sustainable Development Goals (SDGs) 6, 11, 13, and 15, and advancing the development of resilient, flood-adaptive cities in rapidly urbanizing, data-limited environments.