In reply to specticlay:
Yes, some say Yoga, but I think you can do perfectly well with a lot less. These two stretches will help considerably:
http://www.nicros.com/training/articles/stretching-to-improve-high-stepping... .
High-stepping on steep and overhanging walls requires strength, not just flexibility, and in some cases it is a matter of technique. The strength involved is in the abs and the muscles actually involved in lifting the leg. So I've found that the table high-step stretches mentioned in the link above are better done as a step-up exercise. Put both hands on the table palms down as for a mantel and try to step up as close to them as possible. Then do the stretching part, step down, and repeat with the other leg. You'll feel the ab involvement right away I think. To build up the leg strength needed to get the leg up high, try doing the same exercise with ankle weights.
The technique part involves facing sideways rather than straight-in and levering the body away from the rock to get more clearance for the high-step.