While the tropical Pacific teleconnection to North America has been studied extensively, the impact of the Indian Ocean on North American climate has received less attention. Here, through observational analysis and hierarchy atmospheric model simulations with different complexity, we find that the Indian Ocean plays a crucial role in North American winter climate through a teleconnection termed the Indian Ocean - North America pattern. We show that in the warm Indian Ocean phase, this teleconnection contributes to anomalously cold winters along the west coast of the United States through advection with increased mountain snowfall, while simultaneously leading to warmer conditions over the Great Lakes region. Snow-albedo feedback amplifies these Rossby wave-induced surface anomalies. Remarkably, this teleconnection pattern is at work on both interannual and multi-decadal time scales, with its climatic impact being slightly less pronounced than that induced by tropical Pacific sea surface temperature anomalies. Our findings underscore the significance of the Indian Ocean in both the prediction and future projection of North American climate.