Ice adhesion is known to be higher on stiff metallic surfaces and lower on compliant polymeric surfaces. In designing icephobic surfaces, while one approach is to use surfaces with lower stiffness, such surfaces typically exhibit poor wear resistance. The aim of this study is to create a patterned surface with differential stiffness such that there is always a shared contact between stiff and compliant surfaces, and to study the possibility of such surfaces having an optimal balance between low ice adhesion and favorable wear resistance. Patterned surfaces with alternating layers of stiff aluminum and compliant polyurethane elastomer were fabricated, and ice adhesion and wear behavior of such patterned surfaces are reported. Ice adhesion as a function of the metal-polymer contact area ratio was studied, and patterned surfaces exhibited reduced ice adhesion compared to a plain aluminum surface. Reciprocating ball-on-flat sliding tests were used to study the wear behavior of the surfaces. Wear resistance of the patterned surfaces is presented in terms of wear depth, and the patterned surfaces exhibited higher wear resistance than plain polyurethane surface. Simple finite element modeling was used to arrive at stress states of the patterned surfaces and to understand their wear behavior. The novel surface engineering approach outlined in this paper shows promise for realizing durable icephobic surfaces under contact conditions.