Adaptation is the essential process by which an organism becomes better suited to its environment. The benefits of adaptation are well documented, but the cost it incurs remains poorly understood. Here, by analysing a stochastic model of a minimum feedback network underlying many sensory adaptation systems, we show that adaptive processes are necessarily dissipative, and continuous energy consumption is required to stabilize the adapted state. Our study reveals a general relation among energy dissipation rate, adaptation speed and the maximum adaptation accuracy. This energy-speed-accuracy relation is tested in the Escherichia coli chemosensory system, which exhibits near-perfect chemoreceptor adaptation. We identify key requirements for the underlying biochemical network to achieve accurate adaptation with a given energy budget. Moreover, direct measurements confirm the prediction that adaptation slows down as cells gradually de-energize in a nutrient-poor medium without compromising adaptation accuracy. Our work provides a general framework to study cost-performance tradeoffs for cellular regulatory functions and information processing.