Aerobic granular sludge is attractive for high-rate biological wastewater treatment. Biomass wash-out conditions stimulate the formation of aerobic granules. Deteriorated performances in biomass settling and nutrient removal during start-up have however often been reported. The effect of wash-out dynamics was investigated on bacterial selection, biomass settling behavior, and metabolic activities during the formation of early-stage granules from activated sludge of two wastewater treatment plants (WWTP) over start-up periods of maximum 60 days. Five bubble-column sequencing batch reactors were operated with feast-famine regimes consisting of rapid pulse or slow anaerobic feeding followed by aerobic starvation. Slow-settling fluffy granules were formed when an insufficient superficial air velocity (SAV; 1.8 cm s−1) was applied, when the inoculation sludge was taken from a WWTP removing organic matter only, or when reactors were operated at 30°C. Fast-settling dense granules were obtained with 4.0 cm s−1 SAV, or when the inoculation sludge was taken from a WWTP removing all nutrients biologically. However, only carbon was aerobically removed during start-up. Fluffy granules and dense granules were displaying distinct predominant phylotypes, namely filamentous Burkholderiales affiliates and Zoogloea relatives, respectively. The latter were predominant in dense granules independently from the feeding regime. A combination of insufficient solid retention time and of leakage of acetate into the aeration phase during intensive biomass wash-out was the cause for the proliferation of Zoogloea spp. in dense granules, and for the deterioration of BNR performances. It is however not certain that Zoogloea-like organisms are essential in granule formation. Optimal operation conditions should be elucidated for maintaining a balance between organisms with granulation propensity and nutrient removing organisms in order to form granules with BNR activities in short start-up periods.