Strategic structures can benefit from the characteristics of Ultra High-Performance Concretes (UHPC) to achieve long term durability without substantial maintenance. However, in some cases the aforesaid structures may still need to be dismantled. Thus, the possibility to recycle UHPC can significantly affect the environmental impacts associated with the use of this category of materials, given the high binder content and embodied energy. This study has investigated the self-healing performance of a UHPC made with recycled UHPC. Two different mixes were studied, with total replacement of sand and partial replacement of cement by recycled UHPC aggregates and recycled UHPC aggregates and fines respectively. The self-healing capacity of the mixes was addressed with mechanical and durability tests up to six months, with continuous exposure to a chloride-rich solution, simulating the marine environment. The unhydrated cement particles preserved the self-healing capacity of the parent UHPC. Both mixes proved their crack-sealing potential even with repeated damage-healing cycles, exhibiting a slight decrease only after six months of exposure and cracking. The crack closure resulted in a constant mechanical performance which was maintained over time.