I read this book between 1996-1998. It was paperback, and actually quite thick. The artwork was something reminiscent of:
I don't think it was Tad Williams book, but the size of his paperbacks and the artwork are reference points. I believe that the main character was a swordsman looking for something. And the word "Night" is quite relevant, but I'm not certain how. I want to say that there was something about being skilled with a sword earned a rank or a sword or something.
I wish I had more to go on, but if I think of anything, I'll be sure to edit.