Breast cancer patients’ perceived risk of recurrence has been associated with psychological distress. Little is known about the change of patients’ perceived risk of recurrence over time and factors associated with their recurrence-risk perceptions. We prospectively recruited 549 newly diagnosed early-stage breast cancer patients; patients completed interviews at 6 weeks, 6 months, 1 year, and 2 years after definitive surgical treatment. A random-effects regression model with repeated ordinal measurements was used to estimate the relationship between perceived risk of recurrence and demographic, medical, and psychosocial factors. We analyzed data from 535 patients [34% ductal carcinoma in situ (DCIS); 20% non-white] who reported their perceived risk at one or more interviews. At the first interview, 16% reported having no lifetime risk of recurrence, and another 16% reported ≥50% risk of recurrence, including 15% of DCIS patients. Patients who were white (OR = 5.88, 95% CI 3.39–10.19) and had greater state anxiety (OR = 1.04, 95% CI 1.02–1.07) were more likely, while patients who received radiotherapy (OR = 0.72, 95% CI 0.54–0.96) and had more social support (OR = 0.59, 95% CI 0.46–0.75) were less likely to report higher risk of recurrence. Cancer stage was not significantly associated with perceived risk of recurrence. Perceived risk of recurrence did not change significantly over time. Educating early-stage breast cancer patients about their actual risk could result in more realistic recurrence-risk perceptions, and increasing social support could help alleviate anxiety associated with exaggerated risk perceptions.