This thesis studies different ways to construct categories admitting an algebraic K-theory spectrum, focusing on categories that contain some flavor of underlying algebraic structure as well as relevant homotopical information. In Part I, published as [20], we show that under certain technical conditions, a cotorsion pair $(C,C^\bot)$ in an exact category E, together with a subcategory $Z\subseteq E$ containing $C^\bot$, determines a Waldhausen structure on C in which Z is the class of acyclic objects. This yields a new version of Quillen's Localization Theorem, relating the K-theory of exact categories $A\subseteq B$ to that of a cofiber. The novel approach is that, instead of looking for an exact quotient category that serves as the cofiber, we produce a Waldhausen category, constructed through a cotorsion pair. Notably, A need not be a Serre subcategory, which results in new examples. In Part II, joint work with Brandon Shapiro, we upgrade the K-theory of (A)CGW categories due to Campbell and Zakharevich by defining a new type of structures, called FCGWA categories, that incorporate the data of weak equivalences. FCGWA categories admit an $S_\bullet$-construction in the spirit of Waldhausen's, which produces a K-theory spectrum, and satisfies analogues of the Additivity and Fibration Theorems. Weak equivalences are determined by choosing a subcategory of acyclic objects satisfying minimal conditions, which results in a Localization Theorem that generalizes previous versions in the literature. Our main example is chain complexes of sets with quasi-isomorphisms; these satisfy a Gillet--Waldhausen Theorem, yielding an equivalent presentation of the K-theory of finite sets.