We define negative K-groups for exact categories and for ``derived categories'' in the framework of Frobenius pairs, generalizing definitions of Bass, Karoubi, Carter, Pedersen and Thomason. We prove localization and vanishing theorems for these groups. Devissage (for noetherian abelian categories), additivity, and resolution hold. We show that the first negative K-group of an abelian category vanishes, and that, in general, negative K-groups of a noetherian abelian category vanish. Our methods yield an explicit non-connective delooping of the K-theory of exact categories and chain complexes, generalizing constructions of Wagoner and Pedersen-Weibel. Extending a theorem of Auslander and Sherman, we discuss the K-theory homotopy fiber of E^\oplus --> E and its implications for negative K-groups. In the appendix, we replace Waldhausen's cylinder functor by a slightly weaker form of non-functorial factorization which is still sufficient to prove his approximation and fibration theorems.