On 26 October 1986 as part of the deregulation of bus services, West Midlands Travel was formed. It was previously the bus operations of the West Midlands Passenger Transport Executive, which ceased to be a bus operator, but successor organisation Transport for West Midlands retains a co-ordinating role, funding infrastructure like bus stations, providing information, paying for socially necessary services, and concessionary fares. West Midlands Travel remained in public ownership under the West Midlands Passenger Transport Authority until December 1991, when it was sold in an employee share ownership plan to its management and employees for £70 million.^[5]

In April 1995 the company merged with National Express, and in September 1996 rebranded as Travel West Midlands. In November 2002 the Coventry services were rebranded Travel Coventry.^[6]

The former Travel Your Bus and Travel Merry Hill subsidiaries have been merged into the main fleet.

In February 2008 as part of a rebranding of all National Express subsidiaries, it was renamed National Express West Midlands, with the adopted red and white livery being the sixth livery to be used by the company.^[7][8][9] The Coventry service was also rebranded as National Express Coventry.^[10] A seventh livery of crimson and maroon was introduced from 2015 starting with Birmingham routes 9 and 50. Following the announcement that National Express West Midlands will have an entirely electric bus fleet by 2030, a new grey livery, similar to that of the current livery used for platinum vehicles, was introduced for the incoming electric vehicles in 2022.

National Express West Midlands aimed for the whole fleet to be low floor by March 2010.^[11] This was achieved in July that year, with the withdrawal of the final MCW Metrobus in operation at Acocks Green garage.^[12]

In February 2020, National Express announced its intention to operate a completely zero-emission bus fleet by 2030, pledging it would not buy another diesel-powered bus and only purchase zero-emissions vehicles for its West Midlands, Coventry and Dundee operations from 2020 onwards.^[13] The company's first nine Alexander Dennis Enviro400EV battery electric buses began operation on 5 July 2020,^[14] with 20 hydrogen fuel cell-powered Wright StreetDeck Hydroliner buses following in late 2021.^[15][16]

Further hydrogen-powered buses are set to enter the fleet following funding from the Department for Transport.^[17][18] A total of 124 hydrogen buses are due to enter service by 2024, including new articulated vehicles for Sprint cross-city services, initially linking Walsall and Solihull via Birmingham City Centre. The introduction of these new buses will give Birmingham the largest hydrogen bus fleet in Europe.^[19]

At the end of April 2008, NXWM in conjunction with Centro, Dudley Council and other operators, re-routed, re-timed, and renumbered buses in the Dudley, Halesowen and Stourbridge areas.

Following this, a similar process took place in Solihull in January 2009, with one also taking place in October 2009 for South West Birmingham.

In April 2010 a network review for Walsall North (Bloxwich, Brownhills & Aldridge) took place, with another taking place at the end of July 2010 for West Birmingham.

The first review of 2011 was in March for services in East Birmingham/North Solihull,^[20] followed by a review of services in Wolverhampton and West Walsall in July 2011.^[21]

In October 2012 there was a network review in Sandwell, with the final review taking place in June 2013 for North Birmingham, although this was heavily criticized for the small number of routes that were actually changed and those that were being mostly in the Pheasey area.

A network review for areas around West Birmingham, West Bromwich, Oldbury and Blackheath was sought by passenger views in 2017. These changed in April 2017.^[22]

In 2016, a bus service review for east Birmingham, North Solihull and Chelmsley Wood was made by allowing passengers to give their views on the routes. The services were changed in June 2017.^[23]

At the end of 2017, a network review took place for South Birmingham. The public were asked for their opinions on the changes. As of February 2018, the answers received were currently being looked at by the company.^[24] As of 22 July 2018 the network had been changed providing a much simpler network, more express buses and more direct links to the Queen Elizabeth hospital and The University of Birmingham.^[25]

A review of services in Dudley and Sandwell was launched in early 2019 with a planned introduction date of April 2019.^[26] However due to mostly negative feedback, changes were delayed until later in the year. The changes resulted in numerous route number changes with new routes such as service 8 from Wolverhampton to Wollaston Farm via Dudley and Stourbridge.^{[27] [28]}

NXWM operate nine garages: Acocks Green, Birmingham Central (Digbeth), Perry Barr, Yardley Wood, Pensnett, Walsall, West Bromwich, Wolverhampton and Coventry, with the latter trading as National Express Coventry. Perry Barr is the newest location, having opened in December 2022. The site, housing infrastructure for charging a fleet of electric buses and a bus driving simulator as well as featuring 150 solar panels, environmentally-friendly heating systems and water recycling for the three bus washes on site, replaces the 90-year-old original site, which was deemed unsuitable for modernisation and housing charging infrastructure.^[29]

Prior to the construction of the new Perry Barr garage, Bordesley Green garage was the newest location, having opened in 2005. Bordesley Green was also the head office for National Express West Midlands, which replaced the original WMPTE offices in Summer Row, Birmingham. Following the closure of Bordesley Green garage, the head office has relocated to National Express Group head offices in Digbeth.

NXWM previously operated five travel shops located in Dudley, Coventry Pool Meadow bus station, West Bromwich bus station, Birmingham, Corporation Street and Walsall bus station. All offices sold all types of Travelcards, National Express coach tickets and assist customers with information and route planning.^[30] The travel shop at Wolverhampton bus station is unique in that it was the only travelshop within a bus station not operated by NXWM, instead being operated by Transport for West Midlands (previously Centro then Network West Midlands), a division of the West Midlands Combined Authority. In October 2021, National Express West Midlands announced that they were closing all of their travel shops; this was apparently due to people preferring to buy their tickets online and fewer people visiting their shops.^[31] The travel shop in Wolverhampton closed permanently on 1st April 2023.

Previously garages in Stourbridge, Dudley, Merry Hill (part of Travel Merry Hill), Harts Hill, Sutton Coldfield, Hockley, Cotteridge, Selly Oak, Wolverhampton (Cleveland Road), Washwood Heath and Quinton have been operated. The Dudley garage closed on 28 August 1993 to make way for the Dudley Southern By-Pass (which opened in 1999) and was replaced, along with the former Travel Merry Hill depot, by a depot at Pensnett. In July 2010, Lea Hall depot closed. Bordesley Green garage closed in 2022 following the sale of the land in and around the depot for redevelopment.

Crime (such as robbery and assault) and vandalism were, for a period, a persistent problem on NXWM buses, with travel on the upper deck sometimes being particularly challenging. The installation of CCTV on buses was part of the failed attempt to stabilise the level of crime. In the 2009–10 accounting period, 3,341 incidents were recorded on West Midlands buses, including theft, property damage, and drug possession.^[32]

National Express West Midlands is part of the Safer Travel Partnership, created in 2005. Its members also include Centro (responsible for bus, train and tram transport in the West Midlands) and West Midlands Police. The partnership is committed to reducing crime and anti-social behaviour across the West Midlands bus network whilst providing reassurance to the travelling public. The partnership achieves this through a variety of tactics including Gateway Operations. These operations are intelligence led and are based on the established link between those who evade paying their fare and those responsible for crime, disorder and anti-social behaviour. The operation involves partners including NX Revenue Inspectors and Police Officers and Police Community Support Officers from the dedicated Safer Travel Police Team. The activities of the partnership have resulted in very significant reductions in recorded crime across the West Midlands bus network.

Most of the cost of Safer Travel is met from public funds, rather than those of NXWM. This contrasts with most commercial enterprises, such as football clubs, which have to pay a substantial amount for policing.

The Safer Travel name is also used for presentations for schools "educating children about how to respect their buses".

The "See Something, Say Something" campaign, where passengers are encouraged to anonymously send information about nuisance behaviour on buses by text message, has led to 134 arrests and a cut in crime of 15% since April 2010. Crime on the West Midlands bus network has fallen to its lowest level in the last five years.^[33]

In 2015, National Express West Midlands launched the Platinum brand. The Platinum range of buses is a premium brand which offers passengers extra legroom, high backed seats, next stop announcements (on supported services), free Wi-Fi and USB charging on a select series of routes in the West Midlands. The Platinum brand uses Alexander Dennis Enviro400 MMCs, Alexander Dennis Enviro400EVs and Wright StreetDeck Hydroliners, which are usually painted in a grey and red colour scheme. However, they may come in different color schemes for select services such as the 8/X8, 9, 16, 50 and 82/87. Drivers will wear a grey and red suit to match, but there are no suits to match colored liveries.^[34][35]

Deliveries of the first Platinum buses began in 2015, with 58 Alexander Dennis Enviro400 MMCs from a larger order of 171 buses delivered with Platinum branding. These were initially deployed on services 900 and 957, since renumbered X1 and X2,^[34][35][36] before being rolled out onto services 934, 935, 936, 997 and X51 later in the year. The Platinum brand would be extended out into the Black Country in 2016 with the delivery of a further 96 Platinum Enviro400 MMCs resulting in Platinum buses being cascaded from Birmingham Central garage to Pensnett for the Merry Hill to Birmingham X10 service,^[37][38] and then would expand to Harborne in December 2017 with the delivery of 38 new buses.^[39] The Platinum brand would further expand again in 2018 with the delivery of 72 more Enviro400 MMCs, some of which would be delivered to National Express Coventry for the city's first Platinum services, and the West Midlands buses operating on routes connecting Stourbridge, Druids Heath and Chelmsley Wood with central Birmingham.^[40][41]

National Express West Midlands' first zero-emissions Enviro400EV buses were built to Platinum specification, and entered service in July 2020 on route 6 from Birmingham to Solihull via Shirley.^[14] The fuel cell electric Wright StreetDeck Hydroliner FCEV's that followed entered service on route 51 from Birmingham to Walsall via Perry Barr.^[15][16]

The table below show the fleet of vehicles operated by National Express West Midlands. It does not include national/airport coaches based at the company's garages, or buses operated by sister company National Express Coventry.^[42]

• Official website