The club was founded in 1932 as HASK (Hanrievski amaterski sportski klub). During its history, the club was also known as Lokomotiva, Rudar, Industrijalec, and Jugokokta. The club received its current name in the 1989/90 season in commemoration of Gjorče Petrov, a revolutionary considered an important figure of the Macedonian national movement in the Republic of Macedonia.
Makedonija entered the Macedonian First League when Macedonian Republic League transformed in to First League in 1992. They were relegated in 1993/94 season. After playing one season in the Macedonian Second League they were back in the top division. In the 1997/98 season they finished third and qualified to play in the Intertoto Cup, where they played against NK OlimpijaLjubljana from Sloveniain the first round, and SC Bastia from France in the second. In the 2001/02 season they were relegated again, and played three seasons in the second division. Makedonija GP returned to the First League in the 2005/06 season with their best performance, finishing second. They played in the qualifying rounds of the UEFA Cup 2006-07, where they lost to Bulgarian side Lokomotiv Sofia 3-1 on aggregate.
After Makedonija GP quit the first league at the 2009-10 season, the club was unable to participate at any senior level, however the clubs board took over a third tier club MFK Treska from the nearby village of Šiševo, moving the team to Makedonija´s stadium, and became supported by the old Makedonija´s fans. MFK Treska won the Macedonian Third League North promotion play-off in 2010-11, and had been playing in the Macedonian Second League in the 2011-12 season with ambitions to gain promotion to the top flight by sharing the top place on the table after the first round of the season. The name change request was expected for some time now, and the Football Federation of Macedonia, on January 10, 2012, finally accepted the request by MFK Treska to change its name and become officially registered as FK Makedonija Gjorče Petrov, name under which they will compete for the rest of the season.
Makedonija Gjorče Petrov always had loyal fans by its side, mainly the residents of the former Hanrievo, now known as the suburb and municipality Gjorče Petrov. The beginnings of an organised cheering were in 1988, when the first supporter’s transparent appeared on the Kokta stadium, witch is the popular name for the Gjorče Petrov stadium. The current group of supporters are known as Division Hanrievo.