Storey made his England debut under Alf Ramsey on 21 April 1971, in a 3–0 win over Greece at Wembley in a qualifying game for UEFA Euro 1972. Despite at the time being used as a midfielder at club level he played at right-back as Ramsey wanted to assess his options at the full-back position; his rivals for the number 2 shirt were Keith Newton (Everton), Emlyn Hughes (Liverpool), Paul Reaney (Leeds United), Chris Lawler (Liverpool), and Paul Madeley (Leeds United). He almost did not play the game as Arsenal manager Bertie Mee ordered both Storey and teammate Bob McNab to pull out of the fixture to play a league game against Burnley the day before, but was allowed to play for England after coach Don Howe persuaded Mee to reconsider his decision. Storey picked up an assist in the match after providing the cross for Francis Lee's late header. His second cap came in a 1–0 British Home Championship win over Northern Ireland at Windsor Park, in which he played in midfield and man-marked George Best.