Vejvoda arrived at Dukla Prague in 1960, winning the Czechoslovak First League in his first season. With Vejvoda in charge, the club went on to win consecutive league titles in 1961–62, 1962–63 and 1963–64. The club only managed to finish eighth in the 1964–65 season, and he left the club midway through the 1965–66 season, although the club went on to win another championship under Vejvoda's replacement, Bohumil Musil. Vejvoda returned to Dukla in 1969, in the fifth round of the 1969–70 Czechoslovak First League. The team eventually finished the season in seventh position. In three further full seasons with the club, they failed to win another title, finishing 13th, third and fourth. Vejvoda's third spell at Dukla commenced in 1975, replacing Josef Masopust as manager from the sixth round of the 1975–76 Czechoslovak First League. The club finished the season in fourth place before winning the league in 1976–77 and 1978–79, taking Vejvoda's record to six championships with the club. In the 1977–78 season the club finished second, and they finished fourth in 1979–80, which was to be Vejvoda's final season in charge of the Prague club Under Vejvoda, Dukla won six of their eleven league championships.