We report an investigation of the structural and dynamic properties of mixtures of food colloid casein micelles and low molecular weight poly(ethylene oxide). A combination of visual observations, confocal laser scanning microscopy, diffusing wave spectroscopy, and oscillatory shear rheometry is used to characterize the state diagram of the mixtures and describe the structural and dynamic properties of the resulting fluid and solid-like structures. We demonstrate the formation of gel-like structures through an arrested spinodal decomposition mechanism. We discuss our observations in view of previous experimental and theoretical studies with synthetic and food colloids, and comment on the potential of such a route toward gels for food processing.