Denitrification is applied in the tertiary treatment of wastewater to reduce N-pollutants. Fluorescence in situ hybridisation (FISH), CARD (catalyzed reporter deposition)-FISH, cloning, and scanning electron microscopy (SEM) were applied to follow the evolution of the microbial composition and structure of granular sludge in autotrophic denitrifying bioreactors fed with nitrate and thiosulfate. With this goal, FISH oligonucleotide probes for the autotrophic denitrifiers, Thiobacillus denitrificans and Thiomicrospira denitrificans, were designed and their utility tested. CARD-FISH and cloning data showed that bacterial diversity changed with bioreactor operation time. After 110 days of operation, the abundance of Thiobacillus denitrificans cells increased considerably: from 1 to 35% of total DAPI-stained cells and from no isolated clones to 30% of the total positives clones. This fact strongly suggests that this microorganism played a dominant role in the autotrophic denitrification. The Archaeal diversity remained almost unchanged and it was mainly represented by Methanosaeta soehngenii. Scanning electron microscopy results indicated a considerable loss in the integrity of the sludge granules during the operation, with risk of sludge buoyancy.