Legend, History And Fiction

Poul Anderson, The Boat Of A Million Years (London, 1991).

Anderson's fictional immortals interact with legendary and historical figures:

Hanno was Pytheas' navigator;
the legendary Nornagest and Starkadh were immortals;
Hanno tells Richelieu that he met a post-Roman British warlord called Artorius.

In Chapter III, the partnership between Hanno and Rufus begins.
In Chapter V, partnership between Nornagest and Starkadh is impossible because the latter is incapable of cooperation.
In Chapter VI, partnership between Hanno and Svoboda does not begin because they do not recognize each other as immortals.
In Chapter VII, partnership between Hanno and Aliyat is impossible because the latter is incapable of trust.
In Chapter X, the partnership between Asagoa and Tu Shan begins.
Other partnerships will begin in later chapters until the Eight cooperate in the last two chapters, XVIII and XIX.
However, my current rereading has reached only Chapter XI, about Richelieu.