High temperature corrosion of structural alloys in sulfur bearing environments is many orders of magnitude higher than in oxidizing environments. Efforts to increase sulfidation resistance of these alloys include addition of alloying elements. Aluminum additions to iron-chromium alloys bring about increase in sulfidation resistance. This paper reports the effect of pre-oxidation on the sulfidation behavior of Fe-20Cr and Fe-20Cr-5Al alloys in H2-2% H2S environment at 800 °C. The surfaces of sulfidized specimens were also examined. Pre-oxidation of the two alloys results in an incubation period during subsequent sulfidation. After this incubation period, the Fe-20Cr alloy showed sulfidation behavior similar to that when the alloy was not pre-oxidized. The incubation period during sulfidation of the Fe-20Cr-5Al alloy was significantly longer, over 45 h, compared to 2 h for the Al free alloy. Based on the microscopic and gravimetric data a mechanism for sulfidation of these alloys with pre-oxidation has been proposed.