Climate change is a reality, and its impact is being experienced all over the globe. The effects range from heat waves, raising sea levels, coastal erosion, flooding, drought, and reduction of bio-diversity among others. Urban areas are at greater risk since they accommodate the majority of the global human population exceeding 55% and are expected to be 68% by 2050. The most affected urban areas are the tropical coastal cities since most of them fall within low and middle-income countries with low levels of economic development and technological capabilities hence a low capacity to adapt. This study focuses on exploring Nature-Based Solutions (NBS) as an affordable and ecologically sustainable approach to enhance climate change adaptability in tropical coastal cities. A case study of Mombasa is considered, a typical tropical coastal city located in Kenya. Primary data sources including pictures and key informant interviews via snowball sampling were employed to gather ground information. Secondary sources consisted of institutional data review, strategic documents, policies, and scientific journals on NBS and Climate Change adaptation in tropical environments. The study findings depicted the climate change associated challenges in Mombasa include urban flooding, rising sea levels, coastal erosion, increasing temperatures. Rapid urbanization related challenges include inadequate infrastructure and services, poor liquid and solid waste management and inadequate housing. The study proposes NBS measures such as coastal vegetation restoration, implementing green infrastructure in the urban area, and creeks restoration could offer multi-dimensional benefits that can be replicated in other tropical coastal cities to enhance sustainability and climate resilience.