We report the formation of carbyne polysulfide by coheating carbon containing carbyne moieties and elemental sulfur. The product is proved to have a sp2 hybrid carbon skeleton with polysulfide attached on it. The electrochemical performance of carbyne polysulfide as a novel cathode material for rechargeable magnesium batteries is firstly investigated. The material exhibits a high discharge capacity of 327.7 mAh g(-1) at 3.9 mA g(-1). These studies show that carbyne polysulfide is a promising candidate as cathode material for rechargeable Mg batteries if the capacity retention can be significantly improved.