Black band disease (BBD) consists of a mat-forming microbial consortium that migrates across coral colonies causing rapid tissue loss. Although BBD-associated microbial communities have been well characterized, little is known regarding how these complex bacterial consortia develop. This study analyzed successional changes in microbial communities leading to the development of BBD. Long-term monitoring of tagged corals throughout outbreaks of BBD in the central Great Barrier Reef documented cyanobacterium-infected lesions, herein termed cyanobacterial patch(es) (CP), which were macroscopically distinct from BBD and preceded the onset of BBD in 19% of the cases. Dominant cyanobacteria within CP lesions were morphologically distinct from ones dominating BBD lesions. Clone libraries and terminal restriction fragment length polymorphism analysis confirmed shifts within cyanobacterial assemblages, from Blennothrix sp.-affiliated sequences dominating CP lesions, to Oscillatoria sp.-affiliated sequences, similar to those retrieved from other BBD samples worldwide, dominating BBD lesions. Bacterial 16S ribosomal RNA clone libraries also showed shifts in bacterial ribotypes during transitions from CP to BBD, with Alphaproteobacteria-affiliated sequences dominant in CP libraries, whereas gammaproteobacterial and cyanobacterial ribotypes were more abundant in BBD clone libraries. Sequences affiliated with organisms identified in sulfur cycling were commonly retrieved from lesions showing characteristic field signs of BBD. As high sulfide concentrations have been implicated in BBD-mediated coral tissue degradation, proliferation of a microbial community actively involved in sulfur cycling potentially contributes to the higher progression rates found for BBD compared with CP lesions. Results show how microbial colonization of indistinct lesions may facilitate a common coral disease with proven ecological effects on coral populations.