Microbial population dynamics were investigated during the formation of nitrifying granules in an aerobic upflow fluidized bed (AUFB) reactor fed ammonia as a sole energy source. Analyses of clone libraries of 16S rRNA gene and the ammonia monooxygenase subunit A gene (amoA) revealed that although the clones obtained from the seed sludge were widely distributed among the ammonia-oxidizing bacteria (AOB) isolates, the community structure of AOB shifted towards the Nitrosomonas mobilis lineage as granulation proceeded. Quantitative fluorescence in situ hybridization showed that changes in the bacterial population occurred concomitantly with changes in nitrification performance and the size of granules. AOB associated with the N. mobilis lineage were predominant in the early stages as nitrifying granules formed (average diameter, 126 mm). In mature granules (average diameter, 270 mm), at least three types of AOB, N. mobilis, Nitrosomonas oligotropha, and Nitrosomonas europaea, formed different niches and coexisted. Nitrite-oxidizing bacteria (NOB) affiliated with Nitrospira spp. were detected in the start-up period, but were replaced by NOB affiliated with Nitrobacter spp. after granules formed.