An electrodeposition technique has been used for the modification of the fiber-matrix interphase in graphite fiber-epoxy composites. A coating of poly(styrene-co-maleic anhydride) (SMA) polymer was electrodeposited from an aqueous solution on AU graphite fibers used as electrodes in an electrolytic cell. Different electrocoating parameters were initially used to establish the optimum conditions to achieve thin uniform coatings suitable for functioning as interphases in composites reinforced by the coated fibers. The interfacial shear strength (IFSS), evaluated by a single-fiber composite technique, showed that the SMA coating resulted in an improvement of about 50% in IFSS compared with the commercially treated fibers (AS). This was achieved without sacrificing impact strength. Evidence of good epoxy penetration into the coating was obtained by the use of electron microprobe line scans for bromine across the diameter of a filament in a single fiber composite—the bromine introduced through the use of a brominated epoxy resin. The observed improvement in the fiber-matrix interfacial shear strengths is dependent on the co-monomer ratio in electrodeposited SMA.