Shake flask studies on microbial desulfurization of three different coal samples (Indonesian lignite, Chinese lignite and Korean anthracite) were performed to optimize the best suitable growth medium. Among the three different growth mediums (basal salt medium, basal salt medium supplemented with 9 g/L Fe and basal salt medium supplemented with 2.5% S0) tested, the basal salt medium was found to be the best, considering process dynamics and economical factors. The extent of pyrite oxidation was highest with 95% in the experiments with Korean anthracite in basal salt medium supplemented with 9 g/L Fe, while the lowest pyrite oxidation of 70-71% was observed in the experiments with Indonesian and Chinese Lignite’s in only basal salt medium. The microbial sulfur removal in the experiments with basal salt medium supplemented with 9 g/L Fe for all the three coal samples was between 94-97%, while the experiments on basal salt medium supplemented with 2.5% S0 for all the coal samples were relatively much lower ranging between 27-48%. However, the overall study resulted with promising directions for further scaling up of microbial desulphurization in a best growth medium devoid of iron and sulfur supplement.