This paper presents an extensive laboratory testing program undertaken to study the influence of interface bonding and particle size, roughness, and shape on the Young's modulus of ice-saturated frozen sand in triaxial compression. The program also included the influence of particle stiffness by testing plastic beads having a much lower modulus than the quartz-based sand particles. The study used a high-pressure, low-temperature, automated triaxial compression testing system having an on-specimen device capable of consistently measuring displacements of less than 0.1 μm, corresponding to strains of less than 0.0002 %. Very precise temperature and strain-rate control systems contributed to the reliability of the small strain measurements at confining pressures up to 12.5 MPa. Experimental findings show that the Young's modulus of ice-saturated frozen materials varies significantly with particle modulus and increases slightly with particle volume fraction but does not change with confining pressure, strain rate, or temperature. The modulus, however, depends on the ability of the system to transfer interfacial shear stresses between the particle and ice matrix in the form of both adhesion and mechanical interference. In natural frozen sands, the shear stress is transferred primarily through surface roughness and particle angularity, and consequently the adhesional bond between the ice matrix and the sand particles is of secondary importance. In contrast, adhesional bonding dominates in frozen systems composed of relatively smooth spherical particles. Reinforcement theories for two phase particulate composite materials can be used to model the Young's modulus of ice-saturated frozen natural sand.