In this dissertation, we show that that both the generative capacity and the parsing complexity of lexicalized grammar formalisms are systematically related to structural properties of the dependency structures that these formalisms can induce. Dependency structures model the syntactic dependencies among the words of a sentence. We identify three empirically relevant classes of dependency structures, and show how they can be characterized both in terms of restrictions on the relation between dependency and word-order and within an algebraic framework. In the second part of the dissertation, we develop natural notions of automata and grammars for dependency structures, show how these yield infinite hierarchies of ever more powerful dependency languages, and classify several grammar formalisms with respect to the languages in these hierarchies that they are able to characterize. Our results provide fundamental insights into the relation between dependency structures and lexicalized grammars.