Accessibility to social and economic amenities and the provision of a crucial link between production and consumption make transportation infrastructure one of the most crucial factors for a nation's development. This is especially true for landlocked nations like Zambia, which depend on a vast network of both public paved and unsurfaced roads. Poorly maintained roads lead to both macro and micro economic losses, and this study focuses on sustainable prioritization of asphalt-paved road maintenance projects. Regardless of how well-designed or constructed they are, all pavements deteriorate over time as a consequence of the combined effects of traffic loads and the environment which could lead to huge costs of repair and rehabilitation if not addressed effectively. Maintenance treatments slow down the degradation process and so extend the pavement life. The choice of which public road to maintain is a challenging decision that governmental agencies must make that can be addressed by taking a multi-criteria decision-making approach. This study answers the question of which public roads to sustainably prioritize for maintenance considering decision-criteria subject to factors that include physical, climate resilience, socio-economic and environment aspects addressing sustainability concerns. In this study, the authors establish the importance of decision-criteria aspects and develop a score card utility matrix as an objective decision-making tool. In developing this score-card, the authors rely on semi-structured questionnaire guides and Analytic Hierarchy Process (AHP) structured questionnaire approaches in data collection, while adopting a combined AHP and utility matrix approach in developing a score card assessment tool.