Strong and tough natural composites such as bone, silk or nacre are often built from stiff blocks bound together using thin interfacial soft layers that can also provide sacrificial bonds for self-repair. Here we show that it is possible exploit this design in order to create self-healing structural composites by using thin supramolecular polymer interfaces between ceramic blocks. We have built model brick-and-mortar structures with ceramic contents above 95 vol% that exhibit strengths of the order of MPa (three orders of magnitude higher than the interfacial polymer) and fracture energies that are two orders of magnitude higher than those of the glass bricks. More importantly, these properties can be fully recovered after fracture without using external stimuli or delivering healing agents. This approach demonstrates a very promising route towards the design of strong, ideal self-healing materials able to self-repair repeatedly without degradation or external stimuli.