Humans expend more energy walking on uneven terrain, but the amount varies across terrains. Few experimental characterizations exist, each describing terrain qualitatively without any relation to others or to flat ground. This precludes mechanistic explanation of the energy costs. Here, we show that energy costs vary smoothly and approximately quadratically as a function of terrain amplitude. We tested this with healthy adults (N=10) walking on synthetic uneven terrain with random step heights of parametrically controlled maximum amplitude (four conditions 0-0.045 m) and at four walking speeds (0.8-1.4 m s-1). Both net metabolic rate and the rate of positive work increased approximately with amplitude squared and speed cubed (R2=0.74, 0.82, respectively), as predicted by a simple walking model. The model requires work to redirect the body center of mass velocity between successive arcs described by pendulum-like legs, at proportional metabolic cost. Humans performed most of the greater work with terrain amplitude early in the single stance phase, and with speed later in stance during push-off. Work and energy rates changed with approximately linear proportionality, with a ratio or delta efficiency of 49.5% (R2=0.68). The efficiency was high enough to suggest substantial work performed passively by elastic tendon and not only by active muscle. Simple kinematic measures such as mid-swing foot clearance also increased with terrain amplitude (R2=0.65), possibly costing energy as well. Nevertheless, most of the metabolic cost of walking faster or on more uneven terrain can be explained mechanistically by the work performed.