After finishing fifteenth in 2003–04 Bedford entered the play-offs for the final positions in the newly created Conference North and South. They beat Hitchin Town 3–1 in the semi-finals, but lost the final 5–4 to St Albans City. Instead, the club was transferred to the Premier Division of the Southern League for the 2004–05 season. A fifth-place finish in 2005–06 saw them qualify for the promotion play-offs. Following a 1–0 win at Bath City in the semi-finals, they beat Chippenham Town 3–2 in the final to earn promotion to the Conference South. However, they lasted only one season, finishing bottom of the division, and were relegated back to the Southern League.