The stabilization of a mercury-bearing sludge, which is a typical hazardous waste of the chlor-alkali industry in the southern of Taiwan, has been performed by using a cement-fly ash solidification method. A two-stage pretreatment procedure consisting of using sodium sulfide and ferrous sulfate is employed to stabilize the solid end-product. Both the concentrations of the organic mercury in the extraction leachate (C(o)) of the solids matrix, which had not been previously paid much attention to, and of the total mercury (C(t)) have been examined. The results indicate that the two-stage pretreatment greatly enhances the stabilization efficiency of the solid matrix. The value of C(t) can be reduced to a value lower than 1 ppb, which is well below 5 ppb (a Japanese safety regulation on Hg for the in-land sanitary landfill). No organic mercury in the extraction leachate has been detected for the combined process of the two- stage pretreatment and the solidification. Furthermore, within the ranges of experimental conditions of this work, the tendency of C(t) to increase with curing time in the solidification by the process without two-stage pretreatment is greatly prevented by the two-stage pretreatment process. In addition, the 28-day compressive strength of the solid end-product can reach a value larger than 33 kg/cm2, which is well above 10 kg/cm2 (another Japanese regulation).