This study investigates the influence of cutting conditions on surface integrity in the milling of Ti-6Al-4V using various cooling methods: soluble oil coolant; supercritical carbon dioxide; and supercritical carbon dioxide with Minimum Quantity Lubrication. A Design of Experiments approach was used to evaluate a change in direction and interactions between the input factors and the responses. The results show a correlation between the residual stress and the longitudinal/transverse cross-sectional microstructures of the machined surface. It was observed that high-feed milling of Ti-6Al-4V with the assistance of supercritical carbon dioxide with Minimum Quantity Lubrication resulted in improved surface integrity. The opposite was found in terms of soluble oil coolant where some detrimental changes to the microstructure were seen.