Formed in July 1998 as Hillside Trains, a business unit of the Public Transport Corporation, it was privatised in August 1999 becoming a subsidiary of Connex.

The Melbourne Transport Enterprises consortium, consisting of CGEA Transport Asia Pacific Holdings (CTAP) (a subsidiary of CGEA, later known as Connex), GEC Alsthom Australia Ltd (later known as Alstom) and Banque Nationale de Paris, was formed following the announcement to bid on PTC's rail and tram operations.

[1] Hillside Trains, formed on 1 July 1998, took over operation of the Lilydale, Belgrave, Alamein, Glen Waverley, Epping (now Mernda) and Hurstbridge line services.

[2][3][4][5] Melbourne Transport Enterprises successfully bid to take over the Hillside Trains services from 29 August 1999 beating competition from GB Railways and National Express.

An agreement was reached in February 2004 that awarded Connex the exclusive right to operate the entire metropolitan train network from 18 April 2004.

[16][17] Veolia Transport was short listed to bid for the new franchise but lost to Metro Trains Melbourne and ceased operations on 29 November 2009.

[26] When Connex Melbourne took over the M>Train franchise in April 2004, it took over all of its rolling stock including the remaining Hitachi and Comeng sets as well as the Siemens Nexas fleet.

Next day services on eight lines were cancelled and the City Loop closed in the afternoon owing to the extreme weather (at the height of the heatwave) and knock-on effects, and the loss of power at the South Morang transmission station.

In response to the loss of services, the State Government made 30 January a day of free travel on trains, trams and buses.

It was also required to deliver not less than 98% of scheduled train services, and significantly reduce any time spent by passengers waiting due to a delay, over a 1998 benchmark.

In July 2000, an advertising campaign featuring Harry Connick Jr publicised the name change from Hillside Trains to Connex.

The campaign produced by Melbourne advertising agency Cummins & Partners played on the similar sound of Connex and Connick's name.

That's OK, they'll fix the spelling..." Television advertisements featuring Sheena Easton and a trainload of passengers singing her 1980 hit Morning Train (9 to 5) screened during April and May 2004.

On 23 February 2007, a computer hacker broke into the gateway used by the SMS system and sent threatening messages to over 10,000 commuters who had subscribed to the service.