 The aim of the present research is the development of an economically feasible electrochemical method for the extraction of H2S contained in Black Sea waters (CH2S ~9 mg.l−1) and using it as a fuel in an H2S/O2 (air) fuel cell. Low HS− concentrations and the presence of NaCl, similar to the conditions found in the depths of the Black Sea have been investigated. The electrochemical conditions for the oxidation of sulfide HS− directly to sulfite and sulfate on the electrode (anode) catalysts have been found. Different anode catalysts for HS− oxidation have been tested: graphite, cobalt phthalocyanine and perovskite (La1,3Sr0.7NiO4). No catalytic poisoning has been observed by the oxidation products (sulfite and/or sulfate). The characteristics of the sulfide driven fuel cell have been tested with optimized HS− anodes and previously developed oxygen (air) cathodes. An electric power of P = 7.5 mW has been obtained.