Self-healing microcapsules were synthesized by in situ polymerization with a melamine urea-formaldehyde resin shell and an epoxy resin adhesive. The effects of the key factors, i.e., core–wall ratio, reaction temperature, pH and stirring rate, were investigated by characterizing microcapsule morphology, shell thickness, particle size distribution, mechanical properties and chemical nature. Microcapsule healing mechanisms in cement paste were evaluated based on recovery strength and healing microstructure. The results showed that the encapsulation ability, the elasticity modulus and hardness of the capsule increased with an increase of the proportion of shell material. Increased polymerization temperatures were beneficial to the higher degree of shell condensation polymerization, higher resin particles deposition on microcapsule surfaces and enhanced mechanical properties. For relatively low pH values, the less porous three-dimensional structure led to the increased elastic modulus of shell and the more stable chemical structure. Optimized microcapsules were produced at a temperature of 60 °C, a core-wall ratio of 1:1, at pH 2~3 and at a stirring rate of 300~400 r/min. The best strength restoration was observed in the cement paste pre-damaged by 30% fmax and incorporating 4 wt % of capsules.