Aluminum phosphate was deposited onto bundles of carbon fibers and flat glassy carbon substrates using atomic layer deposition by exposing them to alternating pulses of trimethylaluminum and triethylphosphate vapors. Energy dispersive X-ray spectroscopy (EDXS) and solid state nuclear magnetic resonance (SS-NMR) spectra confirmed that the coating comprises aluminum phosphate (orthophosphate as well as other stoichiometries). Scanning electron microscopic (SEM) images revealed that the coatings are uniform and conformal. After coating, the fibers are still separated from each other like the uncoated fibers. Thermogravimetric analysis (TGA) indicates an improvement of oxidation resistance of the coated fibers compared to uncoated fibers.