Formation of sediment in ultra-high temperature (UHT) treated milk has recently been associated with native casein (CN) micelle size and protein composition. This study investigates changes in the protein composition in sub-fractions of UHT treated milk, including sediment, during storage at 40 °C for up to 6 months of milk prepared from milk with either small or large CN micelles. The proteins in sediment were mainly αS1-CN and β-CN and low levels of β-lactoglobulin. The increase of CNs in the soluble phase caused by processing was higher for milk with large native CN micelles. The level of C-terminal derived κ-CN peptides was positively correlated to the level of sediment in the milk. This indicates higher level of removal of κ-CN from the CN micelle with large native size may destabilise the CN micelles causing formation of sediment during storage.