We study the implementation of operations strategy at six German manufacturers in mature businesses. Search theory argues that vertical coordination (i.e., unilateral top-down adjustment of lower-level search actions) balances stability against the improvement potential enabled by frontline search and also that horizontal coordination (i.e., bilateral adjustment among lower-level search actions) is required to ensure compatibility among the initiatives generated in various organizational subunits. Much less is known about how vertical and horizontal coordination interact in operations strategy implementation—that is the focus of this paper. We first study how horizontal and vertical coordination affect the compatibility and creativity of distributed search, triangulating our cross-level interviews with data on the manufacturers’ productivity gains and their strategic projects. We then examine whether and how vertical and horizontal coordination interact. Our case comparisons suggest that leaving either one of them “loose” and keeping the other one “tight” results in a useful balance between compatibility and creativity; in contrast, tightening both types of coordination suppresses creativity and loosening both types risks incompatibility of initiatives across units. These results lead to a theoretical framework that identifies vertical and horizontal coordination as partial substitutes for operations strategy implementation.