Safety concerns are a primary deterrent to bicycling. Bicycle infrastructure is both preferred and safer for bicycling. In this paper, we examine the association between availability of bicycle infrastructure and perceptions of bicycling safety amongst over 3000 bicyclists living in six large Canadian and US cities. In three repeat cross-sectional surveys (2012, 2013 and 2014), adults living in Boston, Chicago, New York, Montreal, Toronto, and Vancouver were surveyed about their bicycling habits, safety perceptions, and demographic characteristics as part of the International Bikeshare Impacts on Cycling and Collisions Study (n = 16,864). Participants were assigned a measure for the availability of bicycle infrastructure (a component of Bike Score® called Bike Lane Score, range 0–100) based on their residential postal code. We used weighted multinomial regression models to examine associations between perceived bicycling safety and the availability of bicycle infrastructure, accounting for sociodemographic characteristics, amongst those who report bicycling in the past month (n = 3446; weighted n = 3493). Overall, 57.9% perceived bicycling in their city as safe, 15.1% as neutral, and 27.0% as dangerous. Our model indicates that, within cities, bicyclists with greater bicycle infrastructure availability had improved odds of perceiving bicycling as safe. Specifically, a 10-unit increase in Bike Lane Score was associated with 6% higher odds of a bicyclist perceiving the safety of bicycling as safe compared to neutral. Bicyclists who are male, younger, lower income, have young children, have a high-school education, and bicycle more frequently are predicted to be more likely to perceive bicycling in their city to be safe. These results suggest that increasing the availability of bicycle facilities by expanding bicycling networks may result in increases in perceptions of bicycling safety for existing bicyclists, but also that individual characteristics play a substantial role in bicycling safety perceptions.