Disclosed are embodiments of an exercise step that utilize spirally shaped air-cushioning legs. The direction of the spiral of the air-cushioning legs is alternated around the periphery of the exercise step to eliminate rotational creep. Flow regulators are utilized to control the flow of air from the top of each of the air-cushioning legs into an interior portion of the base of the exercise step. Spokes provide an air flow passage between the air flow regulators and the central air regulator, as well as providing structural support for the base. Rings are also used around the base that inner connect the spokes and provide additional support. Recessed portions of a lower plate of the base are welded to an upper plate during a blow molding process to add additional support to the base of the exercise step.