Data analytics technology can accelerate the innovation process by enabling existing knowledge to be identified, accessed, combined and deployed to address new problem domains. However, like prior advances in information technology, the ability of firms to exploit these opportunities depends on a variety of complementary human capital and organizational capabilities. We focus on whether analytics is more valuable in firms where innovation within a firm has decentralized groups of inventors or centralized ones. Our analysis draws on prior work measuring firm analytics capability using detailed employee-level data and matches these data to metrics on intra-firm inventor networks that reveal whether a firm’s innovation structure is centralized or decentralized. In a panel of 1,864 publicly-traded firms from the years 1988 to 2013, we find that firms with a decentralized innovation structure have a greater demand for analytics skills and receive greater productivity benefits from their analytics capabilities, consistent with a complementarity between analytics and decentralized innovation. We also find that analytics helps decentralized structures to create new combinations and reuse of existing technologies, consistent with the ability of analytics to link knowledge across diverse domains and to integrate external knowledge into the firm. Furthermore, the effect primarily comes from the analytics capabilities of the non-inventor employees as opposed to inventors themselves. These results show that the benefit of analytics on innovation depends on existing organizational structures. Similar to the IT-productivity paradox, these results can help explain a contemporary analytics-innovation paradox — the apparent slowdown in innovation despite the recent increase in analytics investments.