Proteins and certain carbohydrates contain phenolic moieties, which are potential sites for modification of the function of the biopolymers. In this study, the capability of two different fungal oxidative enzymes, laccase from Trametes hirsuta (ThL) and tyrosinase from Trichoderma reesei (TrT), to catalyze formation of hetero-cross-linking between tyrosine side chains of alpha-casein and phenolic acids of hydrolyzed oat spelt xylan (hOSX) was studied. Formation of reaction products was followed by size exclusion chromatography (SEC), fluorescence spectroscopy, and SDS-PAGE, using specific staining methods for proteins and protein-carbohydrate conjugates. ThL and TrT were observed to differ significantly in their ability to catalyze the formation of protein-carbohydrate conjugates or the linking of the small molecular weight phenolic compounds to alpha-casein. The efficiency of these enzymes to directly cross-link protein also differed notably. TrT was able to cross-link alpha-casein more efficiently than ThL. ThL-catalyzed casein cross-linking was significantly enhanced by ferulic acid, p-coumaric acid, and also hOSX. The main reaction products by ThL appeared to be phenolic acid-bridged alpha-caseins. Indications of hetero-cross-link formation between alpha-casein and hOSX by both oxidative enzymes could be visualized by glycoprotein-specific staining in the SDS-PAGE analysis, although ThL was observed to be more effective in the heteroconjugate formation than TrT.