In this study, the effect of cutting parameters on the quality of an Al/CFRP sandwich structure (aluminium alloy–carbon fibre reinforced polymer) after milling with uncoated and TiAlN-coated tools was examined. The results of the cutting force were also investigated. The research was conducted in a VMC 800 HS vertical machining centre with a variable cutting speed and feed. The milling process was carried out using a non-coated, two-blade carbide milling cutter with a 35° helix angle and an analogous tool with a TiAlN coating. The surface quality was characterised in terms of the height deviation, which is one of the shape deviations after machining hybrid materials. The research showed that the maximum (77.60 µm) and minimum (1.78 µm) values of the height deviations were obtained using the tool with a TiAlN coating. It was found that the tested factors had significant effects on the height deviation, where the feed had the greatest influence and the cutting speed had the lowest influence on the surface quality. The tested factors were not statistically significant in terms of the cutting force.