Cities worldwide are facing several challenges connected to urbanization and climate change. Several cities have identified the implementation of nature-based solutions (NBS) as an option to mitigate several challenges at once. However, can two different aims be reached with NBS in the same location? This question has not yet been addressed. This paper discusses the spatial compatibility of NBS implementation strategies to tackle (1) urban heat island (UHI) effects and (2) water pollution at the same location. The evaluation is based on a spatial analysis of Berlin. We found a positive correlation of high UHI and median high stormwater pollution loads for zinc, total suspended solids, Polycyclic Aromatic Hydrocarbons and Terbutryn. Out of more than 14,000 building/street sections analyzed, 2270 showed spatial matching of high UHI and high stormwater pollution loads. In the majority of building/street sections, stormwater pollution was high for three out of the four parameters. We conclude that the compatibility of NBS implementation for both challenges depends both on the implementation strategies for NBS and on the specific NBS measures. Our spatial analysis can be used for further planning processes for NBS implementation.