A part of Monmouthshire at the time, the station was opened on 9 March 1853 as the second terminus of the Monmouthshire Railway and Canal Company's Eastern Valleys line to Pontypool Crane Street, with an extension to Blaenavon opening the following year. The line itself had opened on 1 July 1852 with an initial temporary terminus situated near Barrack Hill named Marshes Turnpike Gate which closed on 9 March 1853. The initial passenger service between Mill Street and Blaenavon was limited to three Up and Down daily services.
Situated just north of the South Wales Main Line next to Newport High Street station, the station was small and cramped, being situated between a bend in the Monmouthshire and Brecon Canal and Marshes Road (now Shaftesbury Street). A booking office and platforms were provided, with the station's approach line crossing The Marshes on a wooden viaduct. The contract for the construction of the station buildings was awarded to William Fleetwood in November 1852 and the works were completed by May 1853.
The Newport, Abergavenny and Hereford Railway obtained running powers over the Eastern Valleys line with effect from 2 January 1854. The extra traffic which this would generate led to Mill Street being completely remodelled. Extra booking offices were provided and the station's entrance was redesigned to segregate passengers for the different services. An engine shed was provided for NA&HR locomotives as well as accommodation for goods traffic. The first train, a Directors' Special, ran from Mill Street to Hereford on 9 December 1853. The official opening came on 2 January 1854 and the new connection provided services from the Monmouthshire Railway to London, Liverpool, Manchester, Birmingham, Wolverhampton, Stafford, Shrewsbury and Hereford. A daily service of five express trains were provided: two were non-stop from Pontypool (Newport Road) to Mill Street, while the other three were mixed and called additionally at Pontnewynydd.
The arrival of the NA&HR resulted in the doubling of the service frequency at Mill Street, with the new company providing its own services between the station and Coedygric. From 1863 until 1879, the London and North Western Railway also worked out of the station. The station became very busy and congested and calls were made for a new central station to serve Newport which would be nearer the market and have services on the Eastern and Western Valleys lines as well as the South Wales Railway. Agreement could not however be reached with the South Wales and, as an attempt to pacify critics, the Monmouthshire acquired the Mill Pond property at The Marshes for £13,000 to establish a new station. Due to the costs of replacing the wooden viaduct with a stone one, it was decided to fill the marsh with stones and build an embankment to carry the line.
The new station was completed and opened on 28 August 1864. The new buildings were on the site of the NA&HR engine shed and were in timber due to the marshy ground. A new approach was made from Mill Street Bridge to allow hansom cabs to collect and drop off passengers. The station had two platforms, 500 feet (150 m) and 420 feet (130 m) long, covered by a glass canopy supported by bronze pillars supplied by Isca Foundry. The platforms were designed to allow Mill Street to be used as a through station and there was sufficient space to allow five complete trains to be accommodated at any one time. The station was gaslit and passenger waiting facilities were provided. A booking office 46 by 25 feet (14.0 m × 7.6 m) led to parcels and telegraph offices, a superintendent's room and a lost parcels office.3 by 6 feet (0.91 m × 1.83 m)
Once the Eastern Valleys line as far as Marshes Turnpike Gate, attention turned to the construction of an extension as far as the Monmouthshire Railway's Dock Street station on the Western Valleys line. To accommodate the new line, the canal had to be diverted at Dos Foundry. The works were completed by May 1853. However, the connection could not be achieved as originally intended as at a meeting on 14 June 1853 Newport Town Council forbid the use of locomotives between Salutation Junction and Mill Street. As a temporary solution, the width of the canal towpath was extended to provide a temporary line to Dock Street while the canal was diverted. This was completed in August 1853. The double-track from Mill Street to the Docks was opened to traffic in April 1854 and the NA&HR goods traffic was thereafter sent there. Mill Street station continued to act as a passenger terminus as the new connection was only used for freight.
Passenger services did not run between Mill Street and Dock Street stations except for one day in 1927. Due to reconstruction works at Newport High Street, main line services were rerouted via Mill Street, leading to the incongrous sight of a Great Western express trundling through the Newport streets.
The Eastern Valley line prospered for around 20 years until the opening on 17 September 1874 by the Great Western Railway of the Pontypool, Caerleon and Newport Railway which created a parallel route from Newport to Pontypool in order to relieve its Aberdare line. Acknowledging that the Great Western now had the upper hand, the Monmouthshire granted it running rights over the entire network from 1 August 1875. Formal amalgamation of the two companies came with effect from 1 August 1880.
In April 1878, a short connecting branch was opened between Llantarnam Junction on the Caerleon line to Cwmbran Junction on the Eastern Valleys line. On 1 August 1880 a new Cwmbran station was opened on this connecting line, and all Monmouthshire Railway Eastern Valleys trains were diverted via Caerleon to Newport High Street, resulting in the closure of Mill Street station on 1 August 1880.
Mill Street Yard continued to operate for through goods and freight from the Eastern Valley until 27 October 1963 when the line was severed at Oakfield sidings, Cwmbran. The remaining section of line, Crindau sidings - Mill Street Yard - Dock St, closed on 28 November 1966.
The station site has been obliterated by road improvements which have led to its excavation for the Old Green Crossing road complex which passes beneath the South Wales Main Line. The works, which were overseen by Newport Borough Council, were completed in 1975. A reminder of the railway can nevertheless be found in the mural by Kenneth Budd which was commissioned by the Council.