A novel MgO-based binder was developed and applied to treat the anoxic sediment that was collected from Seonakdong river, Korea and was contaminated with heavy metals. The treated sediment was evaluated by measuring compressive strength, expansion, leaching of heavy metals and storage characteristics for $CO_2$. Initially, an optimal blending ratio of lime (L)/fly ash (FA)/blast furnace slag (BFS) that was to be mixed with MgO was screened to be $L_{0.3}-FA_{0.1}-BFS_{0.6}$. Long-term strengths of the sediments that were treated by various mixtures of MgO and $L_{0.3}-FA_{0.1}-BFS_{0.6}$ were then evaluated and the blending ratios between 4 : 6 and 6 : 4 were found optimal, which yielded a compressive strength of 4.09 MPa. On this basis, the optimal MgO-based binder was selected to be a 5 : 5 mixture of MgO and $L_{0.3}-FA_{0.1}-BFS_{0.6}$. The good performance of the MgO-based binder was believed to be due to the formation of Mg $(OH)_2$, which filled the micropores and also increased the density of the solidified matrices. The MgO-based binder exhibited an average stabilizing capacities for heavy metals of 92.9%, which was similar to or higher than that of Portland cement. It was found that 69.1 kg of carbon dioxide could be sequestrated after 365 days of curing when treating a ton of anoxic sediments.