Ensuring safety during door-to-door public transport trips is a fundamental challenge to service providers, as safety influences individuals’ mobility. Using reported safety perceptions of travelers waiting at six bus stops with different characteristics in Stockholm, this study investigates factors that have an impact on determining travelers’ perceived safety and crime perceptions. This is done by assessing the importance of real-time information provision and the environmental characteristics of bus stops during the day and at night for different types of crime, after controlling for travelers’ individual and trip characteristics, and their previous experiences of victimization. Interaction effects of age, gender, and travel frequency are also tested. The results suggest that bus shelter characteristics, natural surveillance, and trustworthy real-time information are the most important factors influencing safety and crime perceptions. Additionally, safety perceptions are strongly influenced by previous experiences of victimization. The effect of perceived feelings about crime and safety are found to be nuanced by age and gender. Unlike some common beliefs, travelers: (1) feel less worried about becoming a victim of crime at bus stops associated with high crime rates; (2) prefer opaque shelters at night; and (3) have higher safety perceptions when the stop is located in an area of mixed land use. The impact of a bus stop’s number of passers-by is found to be insignificant. No direct or indirect effects can be attributed to frequency of travel by bus, indicating that familiar places and routine behavior have no effect on declared crime and safety perceptions.