I think that in the early 90'a Cyprus was a key destination for owner Aspro holidays and IEA based a plane there (in 1992 at least it swapped in Newcastle with the based 757 every Thursday morning - small bit of trivia!)
NCL flights started in 1990 with a single weekly BFS-NCL-LCA and back with leased 733's VH-TAX (Ansett?) or G-MONP.
In 1991 or 1992 NCL became a full summer base with a 757. They acquired c4 757's this year and a 737-400 to join the 733's.
Around 94/95 taken over by Airtours.
Never flew with them.