Penetration depth and substrate characters affect AGS formation and performance. The relationship between substrate gradient and particle size affects AGS stability. The fermentation process is proposed as a pretreatment to improve AGS stability. The influences of flow patterns (mixed-flow and plug-flow) and fermentation pretreatment on aerobic granular sludge (AGS) formation with various substrate availability levels were investigated by running four identical laboratory-scale sequencing batch reactors (R1–R4), comparing two anaerobic feeding strategies and three kinds of substrates. R1 achieved faster granulation with a fast influent fill step followed by a modified anaerobic mixed-flow phase, but the AGS showed poorer stability with a cracked structure and a high suspended solids concentration in the effluent. The anaerobic plug-flow feeding mode (with influent fed slowly from the bottom) in R2 provided deeper penetration depth for the substance to reach the core of AGS and accordingly strengthen AGS stability. An acidogenic up-flow sludge bed reactor was introduced as a pretreatment to improve the AGS performance by enhancing glucose pre-fermentation (R4). AGS fed with mixed volatile fatty acids (VFA) after glucose fermentation showed similar performance compared with the reactor fed with acetate in the aspects of stability, structure, size distribution and nitrogen removal efficiency, and 74% similarity in the microbial community. For actual wastewater with low VFA concentrations, fermentation treatment was suggested as a promising pretreatment for stable AGS granulation and operation.