Effective construction waste management practice is vital for promoting public health and sustainable development. In Edo State, Nigeria, inadequate practices in the construction sector pose health, environmental, and economic risks, yet limited research addresses these challenges. This study examines the challenges to the effectiveness of construction waste management practices and proposes strategies for improvement. A phenomenological qualitative design was employed, using semi-structured interviews with thirty stakeholders, including representatives from construction firms, environmental agencies, and waste management consultancies. Thematic analysis revealed critical challenges such as weak regulatory enforcement, insufficient policies, and the absence of recycling incentives, which undermine progress toward Sustainable Development Goals (SDGs 3 and 11). Contractors further identified high disposal costs and limited knowledge of sustainable practices, while worker-related issues included low awareness and unsafe disposal methods. To overcome these challenges, this study highlighted the need for robust government regulation, investment in waste management infrastructure, and incentives to promote recycling. This study also found that capacity-building initiatives, including comprehensive worker training, are essential to encourage safer and more sustainable practices. In addition, public–private partnerships can strengthen waste collection systems and enhance recycling initiatives. By addressing these issues, this study contributes to filling a knowledge gap in construction waste management within the Edo state context and offers practical strategies for policymakers and industry stakeholders. The findings underscored that sustainable waste management requires a collaborative, multi-stakeholder approach to achieve environmental sustainability and improve public health outcomes.