The airline introduced a restyled livery, as it embarked on an ambitious fleet renewal programme. Two new Airbus A319s, smaller than its other aircraft, were added in 2002. The next year, two new Airbus A330s replaced the older A310s on long-haul routes. A fleet of four Boeing 737s was chosen for the Eurocypria charter subsidiary, however, with two further similar aircraft added in 2004 and 2005. A feature of the new Eurocypria aircraft was that each had a different colour on its tail. In the meantime, the A320s owned by Cyprus Airways but leased to Eurocypria were returned to the parent company.