The pursuit of high-performance, rare-earth-free magnetostrictive materials is crucial for advancing technologies in sensing, actuation, and microelectromechanical systems. Heusler alloys represent a promising, yet underexplored, class of materials for this purpose. In this work, we perform a systematic first-principles investigation of the magnetostrictive properties of 25 Co-based full Heusler alloys, Co₂YZ (Y = V, Cr, Mn, Fe, Co; Z = Al, Ga, Si, Ge, Sn). Our screening identifies 10 compounds with large predicted magnetostriction (|λ₀₀₁| > 100~ppm), highlighted by Co₃Si with a giant value of -966 ppm. Furthermore, we demonstrate two effective strategies for engineering magnetostriction: (i) tuning the Fermi level, which enhances the magnetostriction of Co₃Sn to -905 ppm via Sb doping, and (ii) amplifying the spin-orbit coupling, which boosts the magnetostriction of Co₂CrGa to a colossal -1008 ppm through Re substitution. Our analysis reveals a general predictive rule, uncovering a linear relationship between the magnetostriction and the choice of the Y-site transition metal. This work not only identifies novel candidates for magnetostrictive applications but also establishes clear, physically-grounded design principles to accelerate the discovery of new functional magnetic materials.