The club was founded in 1941 as Goce Delčev and renamed in 1950 to FK Pobeda. FK Pobeda has been a winner of Macedonian First League for two times (eight times as Republic League in Yugoslavia). and Macedonian Football Cup for one time (eight times as Republic Cup in Yugoslavia). Their first great period was the 50's, when they won the Republic Cup for the first time in 1951. One year later Pobeda won its first championship title in 1952 and in 1954 the second one. They waited for 4 years for their next trophy they won the Republic Cup for the second time in 1958. Next year 1959 they became champions of SR Macedonia again. They continued with their winning series in the 60s. Pobeda won its 3rd cup in 1960, and again the cup masters won their 4th cup in 1961. Next year it was time for a new championship title in 1962, and then the duble crown in 1963. Last trophy in the 60's was 1964 Republic Cup for the 6th time. In the late 60's and early 70's Pobeda had a stagnation period although it was on the top most of the time and they played pretty good in the cup too. Finally after 13 years Pobeda won again, and again it was the Macedonian Republic Cup in 1977 for the 7th time. Two years after finally Pobeda was back on the track winning its 5th title after 16 years waiting. Two years after in 1981 Pobeda did it again 7th time champion of SR Macedonia. The 80's was their last good period and they won their 8th championship title in 1986. Next year it was time to win the cup again and they did it for the 8th time in 1987 (and last time in the part of Yugoslavia).
The period of 90s, after a independence of Macedonia, didn't bring much excitement for the Pobeda's fans and they had to wait for better times. The beginning of the 2000s was a good sign and the long period of waiting was over. In 2002 it was time to win the Macedonian Football Cup for the first and only time. Two years later the club was won the champions title in 2004 for the first time since of the Macedonia's independence. They didn't wait for long to win their second, 3 years later in 2007 Pobeda was champion again and for the last time. Also, Pobeda has represented Macedonia for ten times in the European Football Cups. On March 27, 2009, UEFA, the governing body of football in Europe, charged FK Pobeda over match fixing allegations relating to a Champions League qualifying match against FC Pyunik of Armenia in 2004 They were subsequently found guilty and banned from UEFA competitions for eight years. The next season in which they will be eligible to compete is 2017–18.
A successor club which claims rights to Pobeda's honours and records was established in 2010 under the name Viktorija, later renamed to Pobeda Junior. However, they are not legally considered to be successors to the original Pobeda and the two clubs' track records and honours are kept separate by the Football Federation of Macedonia.