Bromley were relegated to Division One again at the end of the 1998–99 season. A fourth-place finish in 2004–05 saw them qualify for the promotion play-offs, and after defeating Metropolitan Police on penalties in the semi-finals, they beat Horsham 3–1 in the final to earn promotion to the Premier Division. In 2006–07 they finished as runners-up in the Premier Division, again qualifying for the promotion play-offs. A 1–0 win over AFC Wimbledon in the semi-finals and a victory against Billericay Town on penalties in the final saw them promoted to the Conference South. The season had also seen them reach the FA Cup first round again, eventually losing 4–1 at Gillingham. Further appearances in the first round were achieved in 2009–10 (against Colchester United), 2011–12 (Leyton Orient), 2012–13 (Fleetwood Town) and 2014–15 (Dartford), but they were beaten on each occasion.