This report investigates the freezing of water droplets on hydrophobic surfaces and reports a means to quantitatively measure the ice-adhesion strength at micro-patterned hydrophobic surfaces. Water droplets were placed on a super-cooled surface where they froze following the heterogeneous nucleation phase-transition. The freezing occurred with two distinct transitions: (a) an initial snapping transition freezing of the external shell of the droplet, and (b) a subsequent bulk freezing of the droplet with a characteristic formation of peaked apex protruding upwardly. To measure the ice-adhesion strength, frozen droplets were sheared from the surface using a Universal Materials Tester (UMT) measuring the resulting knock-off forces. Ice formation and adhesion was investigated on three variations of hydrophobic polydimethylsiloxane (PDMS) surfaces: regularly patterned with high and low surface densities of micro-pillar arrays and non-patterned flat surfaces. Patterning the surfaces was found to accelerate freezing transitions but decrease the measured ice-adhesion strength in correlation with a reduction of total interfacial contact area. However, a more concentrated local stress was observed for the less dense surface structures, indicating a potential area of concern for more fragile systems.