Telehealth promises to provide underserved communities with better medical services and to help rural healthcare institutions become financially sustainable. However, these institutions find it challenging to implement telehealth because their resources are severely constrained even to maintain current operations. This paper investigates how a rural health institution successfully addressed this paradoxical situation by integrating telehealth into its operations over a 20-year period. We identify three sets of tensions that manifest during the telehealth implementation process: autonomy vs. dependence (relating to resource acquisition), controlling vs. drifting (relating to enabling the innovation), and exploration vs. exploitation (relating to creating a sustainable solution). Drawing on Poole and Van de Ven’s (1989) paradoxical approach, we develop four propositions comprising a theory of rural telehealth innovation. We suggest that three paradoxes shape rural telehealth innovation: Paradox of Alliance, Paradox of Governance, and Paradox of Learning, and explain how innovation unfolds in response to these paradoxes.