Malatya station was built in 1931 as part of the contract for the line Fevzipaşa to Diyarbakır. Malatya was the largest city along this line after Diyarbakır. Malatya had already a large fruit industry and was a strategic location with a big military garrison. Malatya was also an historic crossroad to the east, and in 1931, the line to Çetinkaya was already planned. This line would turn Malatya into an important railway junction.
The Danish firm Nyquist and Holm AB (Nohab) was the general contractor for the building of the line Fevzipaşa to Diyarbakır. Nohab which is really a rolling stock manufacturer was in partnership with two fellow building firms: Kampsax and J. Saabye and O. Lerche. These firms made a special "Art Nouveau" design for Malatya station building, which is very different from all the other stations of the line.
The actual construction was done by Abdurrahman Nacı, a Turkish civil engineering firm. It is obvious from the design and from the quality of the work that great care was taken to do this building, which was to be the flagship of line. TCDD respected and maintained the original design and the building still stands as it was.