The following season saw further league re-organisation, with Bedford placed in the new Premier Division; their FA Cup campaign ended with a 4–0 first round defeat at Gillingham. However, the mid-1960s was an extremely successful period for the club in the cup; in 1962–63 they reached the second round where they were again beaten by Gillingham. The following season saw them beat non-League opposition in the first and second round before being drawn against Second Division Newcastle United in the third round. A trip to St James' Park resulted in a 2–1 win for Bedford, before they were defeated 3–0 by Carlisle United in the fourth round in front of a then-record crowd of 17,858. The club were prevented from applying for Football League membership that year as they had signed players from the league without paying transfer fees. The 1965–66 season saw them reach the fourth round again, beating Exeter City 2–1 in the first round, Brighton & Hove Albion 2–1 in a second replay in the second round. Hereford United were then defeated 2–1 in the third round, before a fourth round tie saw them lose 3–0 at home to Everton in front of a record crowd of 18,407. Another cup run in 1966–67 resulted in a second round win over Oxford United before a 6–2 defeat at home to Peterborough United in the third round.