Shorefast sea ice provides an important platform for winter and spring travel between coastal Arctic communities unconnected by road networks. In the past two decades, local Arctic residents have reported thinning and earlier breakup of shorefast ice. Despite these assertions, however, there are few quantitative assessments of how these changes have impacted travel on sea ice. In this study, we use high-resolution satellite remote sensing and transportation modeling to assess snow mobile travel in Uummannaq Fjord, Greenland. Following classification of satellite imagery, we generate optimal least-cost travel routes according to surface types present in the fjord. We then estimate distance and duration of snowmobile travel potential between communities from 1985 through 2019. We find that snowmobile travel in Uummannaq Fjord has potentially become slower and more unpredictable in recent years (2014–2019) relative to thirty years prior (1985–2000), with greater changes for communities located more proximal to the shorefast ice edge. Our results also suggest that reductions in on-ice snow cover impede snowmobile travel more than fractures do. Overall, our analysis demonstrates how remote sensing and transportation modeling may be used to quantify the community-scale impacts of changing shorefast ice conditions and has potential to help manage localized climate-related risk.