Background Despite its health benefits, physical inactivity is pervasive, particularly among those living in lower-income urban communities. In such settings, neighborhood safety may impact willingness to be regularly physically active. We examined the association of perceived neighborhood safety with pedometer-determined physical activity and physical activity self-efficacy. Methods and Findings Participants were 1,180 predominantly racial/ethnic minority adults recruited from 12 urban low-income housing complexes in metropolitan Boston. Participants completed a 5-d pedometer data-collection protocol and self-reported their perceptions of neighborhood safety and self-efficacy (i.e., confidence in the ability to be physically active). Gender-stratified bivariate and multivariable random effects models were estimated to account for within-site clustering. Most participants reported feeling safe during the day, while just over one-third (36%) felt safe at night. We found no association between daytime safety reports and physical activity among both men and women. There was also no association between night-time safety reports and physical activity among men (p = 0.23) but women who reported feeling unsafe (versus safe) at night showed significantly fewer steps per day (4,302 versus 5,178, p = 0.01). Perceiving one's neighborhood as unsafe during the day was associated with significantly lower odds of having high physical activity self-efficacy among both men (OR 0.40, p = 0.01) and women (OR 0.68, p = 0.02). Conclusions Residing in a neighborhood that is perceived to be unsafe at night is a barrier to regular physical activity among individuals, especially women, living in urban low-income housing. Feeling unsafe may also diminish confidence in the ability to be more physically active. Both of these factors may limit the effectiveness of physical activity promotion strategies delivered in similar settings.