Micro-sandblasting pretreatment was applied to AlTiSiN-coated WC–Co tools to enhance cutting performance in 316 L stainless steel milling. An L₉(3³) Taguchi orthogonal array varied passivation pressure (0.1, 0.2, and 0.3 MPa), gun traverse speed (60, 80, and 100 m/min), and tool rotation speed (20, 30, and 40 r/min). Coating thickness varied only from 0.93 to 1.19 μm, and surface roughness remained within 0.044–0.077 μm, confirming negligible thickness and roughness effects. Under optimized conditions, coating adhesion strength and nano-hardness both exhibited significant improvements. A weighted-scoring method balancing these two responses identified the optimal pretreatment parameters as 0.1 MPa, 80 m/min, and 20 r/min. Milling tests at 85 m/min—using flank wear VBₘₐₓ = 0.1 mm as the failure criterion—demonstrated a cutting distance increase from 4.25 m (untreated) to 12.75 m (pretreated), a 200% improvement. Wear progressed through three stages: rapid initial wear, extended steady wear due to Al₂O₃ protective-film formation and Si-induced oxygen-diffusion suppression, and accelerated wear. Micro-sandblasting further prolonged the steady-wear phase by removing residual cobalt binder, exposing WC grains, and offsetting tensile residual stresses. These findings establish a practical, cost-effective micro-sandblasting pretreatment strategy that significantly enhances coating adhesion, hardness, and tool life, providing actionable guidance for improving the durability and machining performance of coated carbide tools in difficult-to-cut applications.