Frühe Jahre

Der Verein wurde 1986 als Betriebsmannschaft der Stadtverwaltung Malatyas unter dem Namen Malatya Belediyespor (dt.: Sportklub der Stadtverwaltung Malatya) gegründet. Er schaffte 1998 und 1999 den Durchmarsch aus dem Amateurlager in die TFF 1. Lig, damals als Türkiye 2. Futbol Ligi die zweithöchste Spielklasse, konnte dort aber die Klasse nicht halten. Das Unterhaus bestand damals aus fünf Gruppen. In der Gruppe 5 war Malatya Belediyespor unter anderem auf Malatyaspor getroffen. Nachdem in der Spielzeit 2000/01 auch der Klassenerhalt in der drittklassigen TFF 2. Lig verpasst worden war, kehrte Malatya Belediyespor wieder in die regionalen Amateurligen zurück, während der Stadtrivale den Wiederaufstieg in die Süper Lig realisierte.

Neuzeit

Malatyaspor stieg im Sommer 2009, also zeitgleich mit dem Aufstieg Malatya Belediyespors in die TFF 2. Lig, in die TFF 3. Lig ab. Um die Stadt besser repräsentieren zu können, versuchte man erneut, Malatyaspor zu übernehmen. Diesen Vorschlag lehnte das Präsidium Malatyaspors ab, und so änderte Malatya Belediyespor statt einer Übernahme seinen Namen in Yeni Malatyaspor um.

Während sich bei Malatyaspor der freie Fall bis in die 6. Liga fortsetzte, kehrte Yeni Malatyaspor 2010 in die Drittklassigkeit zurück. Am Aufstieg in das Unterhaus der Süper Lig scheiterte der Verein mehrfach erst in den Play-offs.

Im Sommer 2012 startete man erneut eine erfolglose Übernahme Malatyaspors. Nachdem auch diese Übernahme gescheitert war, änderte man selbständig den Vereinsnamen in Malatyaspor Futbol Kulübü (kurz: Malatyaspor FK) um, ersetzte das aktuelle Vereinslogo durch eines, das dem Logo Malatyaspors sehr ähnelte, änderte die Vereinsfarben in die von Malatyaspor und versuchte so, eine Übernahme zu erzwingen. Diese Änderungen wurden vom türkischen Fußballbund abgelehnt und Yeni Malatyaspor mit einer Abmahnung versehen. Trotz dieser klaren Abmahnung entschied der Vereinsvorstand, fortan Rot-Gelb, die Vereinsfarben von Malatyaspor, als eigene Vereinsfarben zu verwenden und so an einer Übernahme Malatyaspors weiterzuarbeiten.

In der Spielzeit TFF 2. Lig 2014/15 lieferte sich der Verein mit Pendikspor über einen Großteil der Saison ein Kopf-an-Kopf-Rennen um die Meisterschaft und damit um den direkten Aufstieg. Nachdem der Verein unter der Führung des Cheftrainers Mustafa Uğur zur Rückrunde den Anschluss zu Pendikspor zu verloren drohte, wurde Uğur Anfang Januar 2015 durch Feyyaz Uçar ersetzt. Unter diesem Trainer setzte sich Yeni Malatyaspor gegen seinen ärgsten Verfolger ab und sicherte sich am 31. Spieltag die Meisterschaft der TFF 2. Lig und damit den Aufstieg in die TFF 1. Lig.