Opened in June 1894 as Vodena railway station (Greek: Σιδηροδρομικός σταθμός Βοδενά, romanized: Sidirodromikós stathmós Vodena)^[6][7] in what was then the Ottoman Empire at the completion of the Société du Chemin de Fer ottoman Salonique-Monastir, a branchline of the Chemins de fer Orientaux from Thessaloniki to Bitola. During this period Northern Greece and the southern Balkans where still under Ottoman rule, and Edessa was known as Vodena. Edessa was annexed by Greece on 18 October 1912 during the First Balkan War. On 17 October 1925 The Greek government purchased the Greek sections of the former Salonica Monastir railway^[8] and the railway became part of the Hellenic State Railways, with the remaining section north of Florina seeded to Yugoslavia. In 1926 the station along with the settlement was renamed Edessa.^[6] In 1970 OSE became the legal successor to the SEK, taking over responsibilities for most of Greece's rail infrastructure. On 1 January 1971 the station, and most of Greek rail infrastructure where transferred to the Hellenic Railways Organisation S.A., a state-owned corporation. Freight traffic declined sharply when the state-imposed monopoly of OSE for the transport of agricultural products and fertilisers ended in the early 1990s. Many small stations of the network with little passenger traffic were closed down.

In 2001 the infrastructure element of OSE was created, known as GAIAOSE, it would henceforth be responsible for the maintenance, of stations, bridges and other elements of the network, as well as the leasing and the sale of railway assists.^[1] In 2003, OSE launched "Proastiakos SA", as a subsidiary to serve the operation of the suburban network in the urban complex of Athens during the 2004 Olympic Games. In 2005, TrainOSE was created as a brand within OSE to concentrate on rail services and passenger interface.

Since 2007, the station is served by the Proastiakos Thessaloniki services to New Railway Station. In 2008, all Proastiakos were transferred from OSE to TrainOSE. In 2009, with the Greek debt crisis unfolding OSE's Management was forced to reduce services across the network. Timetables were cut back, and routes closed as the government-run entity attempted to reduce overheads. In August 2013, Proastiakos services where extended to Florina. In 2017 OSE's passenger transport sector was privatised as TrainOSE, currently a wholly-owned subsidiary of Ferrovie dello Stato Italiane^[9] infrastructure, including stations, remained under the control of OSE. In July 2022, the station began being served by Hellenic Train, the rebranded TranOSE.^[10]

The station is still housed in the original brick-built station building. As of (2021) The station is staffed with a working ticket office. The station currently has three platforms; however, only two are currently in use. There are waiting rooms on platform one and waiting shelters on 2. Access to the platforms is via crossing the lines; however not wheelchair accessible. The platforms have shelters with seating; however, there are no Dot-matrix display departure and arrival screens or timetable poster boards on the platforms. There is also Parking in the forecourt.

As of 2020, the station is served on a daily basis by three Reganal trains between Thessaloniki and Florina and 18 Prostiakos terminating this station.^[11] There are no Services to Bitola as the short international connection is now disused, with all international traffic being routed via Idomeni and Gevgelija.

Currently there is a rail-replacement bus between Florina and Edessa.^[12]