Bike-sharing systems are expanding rapidly in metropolitan areas all over the world and individual systems are updated frequently over space and time to dynamically meet demand. Usage trends are important for understanding bike demand, but an overlooked issue is that of “cold starts” or the prediction of demand at a new station with no previous usage history. In this article, we explore a methodology for predicting the bike trips from and to a cold start station in the NYC Citi Bike system. Specifically, gravity-type spatial interaction model and spatial interpolation models, including natural neighbor interpolation and kriging, are employed. The overall results come from experiments of a real-world bike-sharing system in NYC and indicate that the regression kriging model outperforms the other models by taking advantage of the robustness and interpretability of gravity-type spatial interaction regression models and the capability of ordinary kriging to capture spatial dependence.