Basic understanding of formation of aerobic granular sludge (AGS) has mainly been derived from lab-scale systems with simple influents containing only highly diffusible volatile fatty acids (VFA) as organic substrate. This study compares start-up of AGS systems fed by different synthetic and municipal wastewaters (WW), characterised by increasing complexity in terms of non-diffusible organic substrate. Four AGS reactors were started with the same inoculum activated sludge and operated for one year. The development of AGS, settling characteristics, nutrient and substrate removal performance as well as microbial community composition were monitored. Our results indicate that the higher the content of diffusible organic substrate in the WW, the faster the formation of AGS. The presence of non-diffusible organic substrate in the influent WW led to the formation of small granules and to the presence of 20–40% (% of total suspended solids) of flocs in the AGS. When AGS was fed with complex influent WW, the classical phosphorus and glycogen accumulating organisms (PAO, GAO) were outcompeted by their fermentative equivalents. Substrate and nutrient removal was observed in all reactors, despite the difference in physical and settling properties of the AGS, but the levels of P and N removal depended on the influent carbon composition. Mechanistically, our results indicate that increased levels of non-diffusible organic substrate in the influent lower the potential for microbial growth deep inside the granules. Additionally, non-diffusible organic substrates give a competitive advantage to the main opponents of AGS formation – ordinary heterotrophic organisms (OHO). Both of these mechanisms are suspected to limit AGS formation. The presented study has relevant implications for both practice and research. Start-up duration of AGS systems treating high complexity WW were one order of magnitude higher than a typical lab-scale system treating VFA-rich synthetic WW, and biomass as flocs persisted as a significant fraction. Finally, the complex synthetic influent WW – composed of VFA, soluble fermentable and particulate substrate - tested here seems to be a more adequate surrogate of real municipal WW for laboratory studies than 100%-VFA WW.