The aging problem of bitumen leads to pavement failure after years of usage. Microcapsules containing rejuvenator is a promising chemical product applied to improve the self-healing ability of bitumen. The aim of this work was to fabricate and characterize the self-healing microcapsules containing bituminous rejuvenator with nano-inorganic/organic hybrid shells. The shell had a two-layer structure: the inside layer material was the cross-linked methanol modified melamine-formaldehyde (MMF) resin and the outside materials was composed of methanol modified MMF resin and nano-particles of calcium carbonate (nano-CaCO3). The forming mechanism of the two-layer structure was described based on a twice-condensation process. Fourier transform infrared spectroscopy (FT-IR) and Energy Dispersive Spectroscopy (EDS) results confirmed the nano-inorganic/organic hybrid structure of shells. The ideal content of nano-CaCO3 particles was optimized through the morphologies observation. The addition of nano-CaCO3 particles did not greatly influence the mean size of microcapsules. On the contrary, the nano-CaCO3 particles increased the shell thickness of microcapsules owing to the loosely composite structure of shells. Thermal stability tests showed that the microcapsules could survive in the bitumen with a temperature of 200 °C. Moreover, the microcapsules could resist a violent temperature change process without destruction attributing to the protection of nano-CaCO3 particles. The nano-particles on microcapsules decreased the deformation possibility of shells tested by nanoindentation.