Our modern cities are resource sinks designed on the current linear economic model which recovers very little of the original input. As the current model is not sustainable, a viable solution is to recover and reuse parts of the input. In this context, resource recovery using nature-based solutions (NBS) is gaining popularity worldwide. In this specific review, we focus on NBS as technologies that bring nature into cities and those that are derived from nature, using (micro)organisms as principal agents, provided they enable resource recovery. The findings presented in this work are based on an extensive literature review, as well as on original results of recent innovation projects across Europe. The case studies were collected by participants of the COST Action Circular City, which includes a portfolio of more than 92 projects. The present review article focuses on urban wastewater, industrial wastewater, municipal solid waste and gaseous effluents, the recoverable products (e.g., nutrients, nanoparticles, energy), as well as the implications of source-separation and circularity by design. The analysis also includes assessment of the maturity of different technologies (technology readiness level) and the barriers that need to be overcome to accelerate the transition to resilient, self-sustainable cities of the future.