Magnesium (Mg) composites reinforced with carbon-based nanomaterial (CBN) often exhibit low density, enhanced strength, good conductivity, improved wear resistance, and excellent biocompatibility when compared to current industry Mg alloys. This review aims to critically evaluate recent developments in Mg-CBN composites and is divided into five sections: First, a brief introduction to Mg-CBN composites is provided, followed by a discussion of different fabrication techniques for these composites, including powder metallurgy, casting, friction stir processing, and selective laser melting. A particular focus is on the current processing challenges, including dispersion strategies to create homogeneous Mg-CBN composites. The effect of processing on the quantifying disorder in CBNs and distinguishing different sp² carbon materials is also highlighted. Then, the effect of CBN on various properties of Mg-CBN composites is thoroughly analyzed, and the strengthening efficiency of CNTs and graphene in the Mg matrix is examined. Finally, the potential applications of Mg-CBN composites in various industries are proposed, followed by a summary and suggestions for future research directions in the field of Mg-CBN composites.