It provided passenger services on the North Harz network from 2005 to 2018 under the name HEX (HarzElbeExpress).

Connex Sachsen-Anhalt GmbH was founded on 1 July 2004 with its headquarters in Halberstadt, after the responsibility for the public transport services of the North Harz Network (Nordharz-Netz) was transferred to Connex Regiobahn in the preceding March by the state of Saxony-Anhalt.

On 1 April 2008 the KBS 525 line from Leipzig to Geithain was added to the network, and was taken over by Connex Sachsen following a competition.

In December 2008, leadership of the operation went to the newly founded Mitteldeutsche Regiobahn, a brand of Veolia Verkehr Regio Ost.

With the December 2018 timetable change, Abellio Rail Mitteldeutschland replaced Transdev Sachsen-Anhalt as the operator of services on the North Harz network.