O 58016 entrou em serviço em outubro de 1984 e, embora fizesse parte das “primeiras 35” locomotivas, era diferente em muitos detalhes subtis do 58001 “original”. Saiu da oficina com a pintura Railfreight Red Stripe, apresentando chapas laterais da cabine com ângulos diferentes, puxadores nas portas de acesso e um filtro/armadilha de humidade na tubagem do travão de ar. Foi repintado em Triple Grey com a marca Coal Sector em 1989, altura em que já tinha um silenciador de escape largo e pods de rádio NRN no tejadilho da cabine. Em 1991, foi adicionada a placa do depósito das torres de arrefecimento de Toton no lado do segundo maquinista.
Em 1992, o 58016 destacou-se por substituir um serviço Sprinter na linha Cambridge-Birmingham com uma seleção variada de carruagens Mk2. Como muitas outras locomotivas da frota, a marca Coal Sector deu lugar à Mainline, e a locomotiva continuou a operar com a pintura Triple Grey até receber uma vistosa pintura em bordô e dourado da EWS em 1996. O 58016 foi uma das últimas 58 a operar no país pela EWS, sendo retirada em agosto de 2002. Foi escolhida para ser restaurada para a Fertis, o que implicou uma viagem a França. Após o regresso ao Reino Unido, foi colocada em armazenamento no Depósito Diesel de Crewe, onde permaneceu até ser adquirida pelo Grupo de Locomotivas Classe 58 para preservação. Atualmente, a locomotiva encontra-se no depósito da UKRL em Leicester.