The use of polymer matrix composites in aerospace propulsion applications is currently limited by insufficient resistance to erosion by abrasive media. Erosion resistant coatings may provide necessary protection; however, adhesion to many high temperature polymer matrix composite (PMC) materials is poor. A low pressure oxygen plasma treatment process was developed to improve adhesion of CNx coatings to a carbon reinforced, fluorinated polymer matrix composite. Fullerene-like CNx was selected as an erosion resistant coating for its high hardness-to-elastic modulus ratio and elastic resilience which were expected to reduce erosion from media incident at different angles (normal or glancing) relative to the surface. In situ x-ray photoelectron spectroscopy was used to evaluate the effect of the plasma treatment on surface chemistry, and electron microscopy was used to identify changes in the surface morphology of the PMC substrate after plasma exposure. The fluorine concentration at the surface was significantly reduced and the carbon fibers were exposed after plasma treatment. CNx coatings were then deposited on oxygen treated PMC substrates. Qualitative tests demonstrated that plasma treatment improved coating adhesion resulting in an erosion resistance improvement of a factor of 2 compared to untreated coated composite substrates. The combination of PMC pretreatment and coating with CNx reduced the erosion rate by an order of magnitude for normally incident particles.