Steel toe shoes should be replaced when they show signs of significant wear, damage, or when they no longer provide adequate protection. It is recommended to inspect your shoes regularly for signs of deterioration, such as worn-out soles, broken or bent steel toe caps, or any other structural damage.