Recovery criteria for depleted species or populations normally are based on demographic measures, the goal being to maintain enough individuals over a sufficiently large area to assure a socially tolerable risk of future extinction. Such demographically based recovery criteria may be insufficient to restore the functional roles of strongly interacting species. We explored the idea of developing a recovery criterion for sea otters (Enhydra lutris) in the Aleutian archipelago on the basis of their keystone role in kelp forest ecosystems. We surveyed sea otters and rocky reef habitats at 34 island-time combinations. The system nearly always existed in either a kelp-dominated or deforested phase state, which was predictable from sea otter density. We used a resampling analysis of these data to show that the phase state at any particular island can be determined at 95% probability of correct classification with information from as few as six sites. When sea otter population status (and thus the phase state of the kelp forest) was allowed to vary randomly among islands, just 15 islands had to be sampled to estimate the true proportion that were kelp dominated (within 10%) with 90% confidence. We conclude that kelp forest phase state is a more appropriate, sensitive, and cost-effective measure of sea otter recovery than the more traditional demographically based metrics, and we suggest that similar approaches have broad potential utility in establishing recovery criteria for depleted populations of other functionally important species.