DNA-protein cross-linking is one of the many DNA lesions mediated by hydroxyl radicals, the most damaging among the reactive oxygen species in biological systems. Density functional theory methods are employed to investigate the complex reaction mechanisms of the formation of cytosine-tyrosine cross-links as observed in gamma-irradiated aqueous solutions of cytosine and tyrosine, as well as in gamma-irradiated nucleohistone. The majority of the radical addition mechanisms considered are found to have significant barriers and therefore to be thermodynamically unfavorable for the formation of the initial cross-linked product. Our calculated reaction potential energy surfaces suggest that a feasible complete mechanism consists of radical combination forming the initial cross-linked product, a hydrogen shuffle within the initial cross-linked product, and an acid-catalyzed dehydration reaction. Water and hydrogen-bonding interactions are suggested to play a key role in catalyzing the hydrogen-transfer step of the reaction.