Background: Microbiome studies suggest the presence of an interaction between the human gut microbiome and soil-transmitted helminth. Upon deworming, a complex interaction between the anthelminthic drug, helminths and microbiome composition might occur. To dissect this, we analyse the changes that take place in the gut bacteria profiles in samples from a double blind placebo controlled trial conducted in an area endemic for soil transmitted helminths in Indonesia. Methods: Either placebo or albendazole were given every three months for a period of one and a half years. Helminth infection was assessed before and at 3 months after the last treatment round. In 150 subjects, the bacteria were profiled using the 454 pyrosequencing. Statistical analysis was performed cross-sectionally at pre-treatment to assess the effect of infection, and at post-treatment to determine the effect of infection and treatment on microbiome composition using the Dirichlet-multinomial regression model. Results: At a phylum level, at pre-treatment, no difference was seen in microbiome composition in terms of relative abundance between helminth-infected and uninfected subjects and at post-treatment, no differences were found in microbiome composition between albendazole and placebo group. However, in subjects who remained infected, there was a significant difference in the microbiome composition of those who had received albendazole and placebo. This difference was largely attributed to alteration of Bacteroidetes. Albendazole was more effective against Ascaris lumbricoides and hookworms but not against Trichuris trichiura, thus in those who remained infected after receiving albendazole, the helminth composition was dominated by T. trichiura. Discussion: We found that overall, albendazole does not affect the microbiome composition. However, there is an interaction between treatment and helminths as in subjects who received albendazole and remained infected there was a significant alteration in Bacteroidetes. This helminth-albendazole interaction needs to be studied further to fully grasp the complexity of the effect of deworming on the microbiome. Trial registration: ISRCTN Registy, ISRCTN83830814.