Ultra-high temperature (UHT) treatment of milk forms a deposit or fouling in the processing equipment that is mineral-based with an enclosed protein network. This study addresses the fundamental mechanisms that control the removal of this deposit. For this purpose, the structural and compositional changes during the cleaning process have been studied. The structure analysis was performed with scanning electron microscopy (SEM) and confocal laser scanning microscopy (CLSM) on samples that were quenched at different stages of the cleaning process. It was found for acid cleaning that the mineral content is rapidly decreasing in the fouling layer as the cleaning continues, but there is still an intact protein structure with the similar thickness as the original fouling. For alkali cleaning, part of the protein structure was subsequently removed from the outside towards the stain-less steel as a function of time, while the mineral structure was mostly remaining. The break-up of the organic network structure, which likely involves depolymerization of protein aggregates, were found to control the cleaning efficiency. The weakening of the protein network facilitates the removal of the UHT fouling layer during the acid cleaning step and allow for an efficient cleaning cycle. The chemical reactions that occur within the fouling layer between the hydroxyl ions and the protein network was modeled according to a depolymerization reaction and a mechanistic model of the cleaning process is presented.