Cell-matrix adhesion complexes (CMACs) are foci of cellular attachment to the extracellular matrix (ECM). This attachment, mediated by integrins and adaptor proteins, provides both physical and regulatory links between the ECM and the cellular microfilament system. Through continual regulation and rearrangement of both ECM adhesion and actin structures, CMACs constitute core machineries of cell migration. To fulfill this role, CMACs are exceptionally flexible and dynamic complexes, and their components undergo rapid and regulated turn-over to maintain delicately balanced streams of mechanical and chemical information. Besides the critical role of CMACs in cell migration, signaling through these complexes provides influence over virtually every major cellular function, including for example cell survival, cell differentiation and cell proliferation. This review depicts the roles of CMACs in cell migration and discusses how CMACs integrate with other sub-cellular systems involved in cell motility. Importantly, we also present a rationalized view of CMACs as information handling machines, and suggest strategies that may facilitate better understanding of the complex cell migration phenomenon as a whole, through quantitative and integrative (systems biology) approaches.