The capacities of two cyanogenic bacterial strains namely Pseudomonas aeruginosa and Bacillus megaterium for the cyanide production and gold bioleaching from the pure gold particles and a gold-bearing ore (8 ppm) were compared together. Also, in order to maximize the cyanide excretion and subsequently the gold recovery, the influences of the initial pH, glycine, FeSO4, NaH2PO4, and MgSO4 concentrations in the growth media were studied and optimized. In the optimal culture condition, P. aeruginosa and B. megaterium produced 66.35 and 67.05 mg/l cyanide ion, respectively. Bioleaching during the bacterial growth and using the cell-free spent medium showed that the latter improved the Au dissolution by 18%. The concentration of Au in the leachate of B. megaterium reached 205 and 32.2 µg/l for the pure gold and the ore, respectively. Moreover, removing copper and iron before cyanidation increased the Au concentration to 44.4 µg/l.