We provide evidence that perceptions of crime risk are severely biased for many years after a move to a new neighborhood. Based on four successive waves of a large crime survey, matched with administrative records on household relocations, we find that the longer an individual lives in a neighborhood, the higher their perception of the crime rate in the neighborhood. This finding holds irrespective of whether the move is from a relatively low-crime to a relatively high-crime area or vice versa. We find that avoidance behavior adjusts in line with the observed changes in beliefs.