A number of transmembrane proteins have been recently reported to be modified by the covalent addition of saturated fatty acids which may contribute to membrane targeting and specific protein-lipid interactions. Such modifications have not been reported in cell-associated heparan sulfate proteoglycans, although these macromolecules are known to be hydrophobic. Here, we report that a cell surface heparan sulfate proteoglycan is acylated with both myristate and palmitate, two long-chain saturated fatty acids. When colon carcinoma cells were labeled with [3H]myristic acid, a significant proportion of the label was shown to be specifically incorporated into the protein core of the proteoglycan. Characterization of fatty acyl moiety in the purified proteoglycan by reverse-phase high pressure liquid chromatography revealed that approximately 60% of the covalently bound fatty acids was myristate. We further show that this relatively rare 14-carbon fatty acid was bound to the protein core via a hydroxylamine- and alkali-resistant amide bond. The remaining 40% was the more common 16-carbon palmitate, which was bound via a hydroxylamine- and alkali-sensitive thioester bond. Palmitate appeared to be added post-translationally and derived in part from intracellular elongation of myristate, a process that occurred within the first two hours and was insensitive to inhibition of protein synthesis. Acylation of heparan sulfate proteoglycan represents a novel modification of this gene product and could play a role in a number of biological functions including specific interactions with membrane receptors and ligand stabilization.