The club was founded in 1958 as FK Dukla Dejvice and advanced to the Prague Championship in the 1983–84 season. Prior to 2001, the club's best finish in a season had been second in the Prague Championship in the 1984–85 season. In 2001 the club became known as FK Dukla Prague, but not the legal successor of the original Dukla Prague team, which had merged in 1996 to finally become 1. FK Příbram.
The club finished 14th in the 2001–02 Prague Championship and in the same position the following season. It then had a season in the sixth level of Czech football, the 1.A třída.Petr Benetka led the club to the league title in 2003–04, signaling a return for the club to the Prague Championship. The club finished in second place in the 2004–05 season but 13th the following season. In April 2006, Dukla's president Milan Doruška promised that the club would rise up the league system. In November 2006, Dukla Prague management announced that it had agreed to a takeover of second league rights of the Jakubčovice team and in 2007 Dukla took Jakubčovice's place in the Czech 2. Liga, having finished the 2006–07 season in second place.
Dukla Prague played in the Czech 2. Liga from the 2007–08 season, playing their first 2. Liga match on 4 August 2007, which they lost to Opava by a 2–1 scoreline. After four seasons they won the division and gained promotion to the top flight for the 2011-12 season.
The club wear yellow and red, the traditional colours of the club. In October 2008, the club wore black shirts in a league match against Most to commemorate the death of Josef Hájek, the man responsible for the return of league football to Dukla.