The collimation of proton beams accelerated during ultra-intense laser irradiation of thin aluminum foils was measured experimentally whilst varying laser contrast. Increasing the laser contrast using a double plasma mirror system resulted in a marked decrease in proton beam divergence (20° to <10°), and the enhanced collimation persisted over a wide range of target thicknesses (50 nm–6 µm), with an increased flux towards thinner targets. Supported by numerical simulation, the larger beam divergence at low contrast is attributed to the presence of a significant plasma scale length on the target front surface. This alters the fast electron generation and injection into the target, affecting the resultant sheath distribution and dynamics at the rear target surface. This result demonstrates that careful control of the laser contrast will be important for future laser-driven ion applications in which control of beam divergence is crucial.