A major cause of ultrafiltration (UF) membrane fouling in surface water treatment is natural organic matter (NOM). Some studies have reported that heated aluminum oxide particles (HAOPs), prepared by boiling a suspension containing precipitates of the common coagulant alum, can remove substantial amounts of NOM and reduce fouling when they were pre-deposited on UF membranes. However, the influence of the size and structure of the HAOPs in mitigating NOM membrane fouling has not been fully explored so far. This work has investigated the change in microstructure of the HAOPs during the heating process and the subsequent effect on the performance of the membrane process, and especially on the mitigation of fouling. As the heating time increased, the structure of the HAOPs transformed gradually from an amorphous nature to a semi-crystal, and then to a microcrystalline phase. It was found that this micro-crystallization process played a key role in affecting the structural properties of the nano-scale particles and the membrane filtration performance. During the crystalline transition, a change of particle size distribution occurred and the average particle size was found to decrease gradually owing to a dehydration reaction. The smaller particle size of the HAOPs provides a denser pre-filtration layer for NOM separation, and their more rigid structure reduces layer compression and hydraulic resistance during operation. Optimization of the pre-heating condition and surface loading can effectively enhance the performance of the HAOPs layer in reducing NOM fouling in the UF membrane system.