Class 365 was introduced from 17th October 1996 on Connex.
I'm still trying to find out when the first run on the Great Northern line was.
PRISM Rail took over that line on the 5th January 1997 and a search through FLICKR shows some examples still at Doncaster awaiting delivery at the end of March 1997. So I don't even know if they were ever in service for NSE on the GN.