At the time of commencing operations in July 1993, Maersk Air UK operated a fleet of five BAC One-Elevens and three Jetstream 31s out of Birmingham Airport. Routes were flown to Amsterdam, Belfast, Copenhagen, Cork, Dublin, Glasgow, Milan, Newcastle and Stuttgart. As of 1994 it had 185 employees. The airline carried out a major overhaul of its fleet in 1996. The four One-Elevens were sold to Nationwide Air Charter and replaced with newer Boeing 737-500s. Meanwhile, a Jetstream 41 was transferred from British Airways, replacing the smaller Jetstream 31s. The services to Dublin, Cork and Glasgow were terminated and instead a route was started to Lyon.