Looking at my AE logbooks, the first Newcastle I did was on April 27th 1980. We flew From Gatwick to Alicante, then on to Newcastle in B737/200 GBMSM. On the 28th we operated GBJFH from Newcastle - Palma - Manchester.
After 6 years on the B757 my first Newcastle - Bangor, Maine was on May 23rd 1989.