Implementing artificial intelligence (AI) applications in firms promises great potential but poses complex challenges. Especially incumbent firms often struggle to use the full potential of AI, because of paradoxes that arise in the context of implementing AI solutions, such as concerns regarding data privacy but simultaneously sharing personal data excessively. To analyze what paradoxes are caused by the challenge to implement AI in incumbent firms, we draw on the literature on technological paradoxes and followed a qualitative research approach using semi-structured interviews in eight companies on the path to AI implementation. Our results unravel that various mismatches between strategic imperatives and tactical paradigms emerge from three AI paradoxes: the privacy paradox, the potential paradox, and the integration paradox. Our results contribute to the information systems literature on AI and technological paradoxes by providing novel empirical insights on AI paradoxes and practical implications to address these paradoxes in incumbent firms.