1993’s When True Night Falls is the second book in C. S. Friedman’s Coldfire Trilogy.
Having vanquished a Big Bad in the first volume (as explained in the lengthy mission report provided at the beginning of the novel), Damien Vryce (Warrior Priest), Hesseth (a rakh, native to the planet), and Gerald Tarrant (former Prophet of the Church for Human Unification on Erna) head East, pursuing some as yet unidentified great evil they believe resides there.
The expedition is not the first to set out from the West for the East. There have been several previous expeditions, all of which vanished without a trace. Now Damien and his allies get to find out why.