Crime and safety are commonly cited barriers to physical activity (PA). We had three objectives, 1) describe the association between objective crime measures and perceptions of crime, 2) analyze the relationships between each type of crime and accelerometer-measured physical activity in caretakers and young children (ages 3–5 years), and 3) explore for early gender differences in the relationship between crime and physical activity in young children. Data are from the cross-sectional baseline data of an ongoing randomized controlled trial in Nashville, Tennessee spanning September 2012 through May 2014. Data was analyzed from 480 Hispanic dyads (adult caretaker and 3–5 year old child). Objective crime rate was assessed in ArcGIS and perception of crime was measured by caretaker agreement with the statement “The crime rate in my neighborhood makes it unsafe to go on walks.” The primary outcome was accelerometer-measured physical activity over seven consecutive days. Objective and perceived crime were significantly positively correlated. Caretaker vigorous PA was significantly related to perceptions of crime; however, its relationship to objective crime was not significant. Child PA was not significantly related to caretaker perceptions of crime. However, interactions suggested that the relationship between crime rate and PA was significantly more negative for girls than for boys. Objective and subjective measures of crime rate are expected to be important correlates of PA, but they appear to have complex relationships that are different for adults than they are for young children, as well as for young girls compared to boys, and research has produced conflicting findings.