We carry out Born-Oppenheimer molecular dynamic simulations to show that the reaction between the smallest Criegee intermediate, CH2OO, and hydrogen sulfide (H2S) at the air/water interface can be observed within few picoseconds. The reaction follows both concerted and stepwise mechanisms with former being the dominant reaction pathway. The concerted reaction proceeds with or without the involvement of one or two nearby water molecules. An important implication of the simulation results is that the Criegee-H2S reaction can provide a novel non-photochemical pathway for the formation of a C-S linkage in clouds and could be a new oxidation pathway for H2S in terrestrial, geothermal and volcanic regions.