Stokoe made his debut against Middlesbrough on 25th December 1950. He joined a team that included Bobby Cowell, Joe Harvey, Frank Brennan, Jack Fairbrother, Bobby Corbett, Charlie Crowe, Tommy Walker, Alf McMichael, George Hannah, Jackie Milburn, George Robledo and Bobby Mitchell. However, he played in only 9 games that season.
For the next few years Stokoe mainly played in the reserves and was not selected for the FA Cup final wins against Blackpool (1951) and Arsenal (1952). It was not until the 1954-55 season that Stokoe displaced Frank Brennan as the club's centre-half.
Newcastle United had another good FA Cup run in the 1954-55 season, Plymouth Argyle (1-0), Brentford (3-2), Nottingham Forest (2-1), Huddersfield Town (2-0), York City (2-0) to reach the final against Manchester City. Newcastle's star player, Jackie Milburn, later recalled how the game started: "I won a corner on the right and Len White ran over to take it. Manchester City's captain, Roy Paul, was standing next to me as Len placed the ball, but he suddenly yelled, 'Bloody hell, I should be marking Keeble,' so off he darted to find big Vic, who was more widely noted for his prowess in the air. Len fired the ball in my direction and there was I standing all alone like Grey's Monument. I headed the ball past their keeper, Bert Trautmann and that was it."
The situation got worse for City when Jimmy Meadows suffered a serious knee injury in the 18th minute. Just as in 1952 Newcastle had just ten men to beat. Despite this disadvantage City equalized when Bobby Johnstone beat Ronnie Simpson with a diving header after good work from Joe Hayes.
In the second-half Newcastle United made their numerical advantage count. According to Jackie Milburn, the Newcastle captain, Jimmy Scouler, was the best player on the pitch: "Scoular kept spraying great crossfield balls to Bobby Mitchell and between them they tore City apart." Charlie Buchan later commented: "I have never previously seen a wing-half display as good as that of Scoular's in any big game."
In the 53rd minute Bobby Mitchell made a run down the wing before scoring from an acute angle. Soon afterwards George Hannah scored from a pass from Mitchell. Newcastle United had won the FA Cup for the third time in five years and Stokoe had won his first cup winners' medal.
Stokoe was a regular in the Newcastle United team for the next five seasons. He also took over as captain when Jimmy Scouler was unavailable. In February 1961 Stokoe joined Bury as player-manager. He had played in 267 league and cup games for Newcastle.
Stokoe had a long career as manager. This included Bury (1961-65 & 1976-77), Charlton Athletic (1965-1967), Carlisle United (1968-1970, 1980-1983 & 1985-1986), Blackpool (1970-1972 & 1978-79), Sunderland (1972-1976 & 1987-89) and Rochdale (1979–1980). His great success was winning the FA Cup with Sunderland in 1973.
Bob Stokoe died on 1st February, 2004.