Baneservice originated as a division of Norges Statsbaner (NSB), which had performed construction and maintenance functions all the way back to the formation of NSB in 1883. During the 1990s, multiple rounds of reforms and restructurings were enacted upon NSB and the Norwegian railway sector, one of which saw the rise of a new organisation model in 1992 under which infrastructure activities were organised principally under regional managers, which were given more responsibility and consequently reinforced by technical and administrative support functions.^[2] Under this model, the planning department was entirely separated from the department, which became part of Jernbaneverket when NSB was split up in 1996 with the name Jernbaneverket BaneService.

During the early 2000s, the liberal-conservative government sought to pivot from public sector dominance towards a market for public tender bids for the maintenance of the railway infrastructure. To achieve this, it was decided that BaneService was to be separated from Jernbaneverket; around this time, similar policies were being enforced on the Public Roads Administration and Coastal Administration.^[3][4]

Accordingly, during 2005, the maintenance division was demerged, and established as the limited company Baneservice; it was owned directly by the ministry.^[5] This restructuring was part of a program initiated by the conservative-liberal government to privatize the maintenance of the tracks, compelling the administration to perform tenders; The process of privatizing the work of 1,100 employees was discontinued after the 2005 election, following the victory of the socialist coalition government; despite this reversal, the Administration stated its intention to continue to tender various projects where it would be economically desirable to do so.^[2][6] While this government did announce its intention to revert the decision to privatise the maintenance of the railway, BaneService has remained operational as a separate company.^[7]