Engineered Cementitious Composites (ECC) have shown better resistance at high temperatures than conventional fiber-reinforced concretes (FRC). The enhanced high-temperature performance results from a combination of the following features: presence of polymer fibers, lack of coarse aggregates, and high-thermal resistance cementitious matrix. Since the thermal stability of the cementitious matrix significantly affects the high-temperature performance, this study aims to study the influence of magnesium-silicate-hydrate (MSH) based cementitious matrix on high-temperature residual behavior. The MSH cementitious matrix utilizes reactive magnesia cement (MgO-based binder) and silica fume as a reactive silica source. This study experimentally investigates the mechanical performance of MSH-based ECC at sub-elevated temperatures (up to 200 °C). The highest investigated temperature was limited to 200 °C as the polymer fibers [polyethylene (PE)] melt around 160–170 °C. The mechanical performance was characterized under uniaxial tension (tensile strength and ductility) and compression under residual testing conditions. The study showed a linear reduction in residual compressive strength and first cracking strength of the MSH-ECC. The tensile ductility was completely lost after the melting of PE fiber above 150 °C, showing a remarkable drop in both tensile strength and strain capacity at 200 °C. The XRD characterization, however, showed no noticeable changes in the chemical composition of the cementitious matrix, and observed damages were primarily attributed to physical causes.