Byzantium's Crown
Byzantium's Crown is a 1987 alternate history novel with fantasy elements by Susan Shwartz. It is the first volume in the trilogy Heirs to Byzantium, which also includes Queensblade and The Woman of Flowers.
The novel's plot concerns dynastic power struggles in a history in which Mark Antony defeated Octavius (who never became Augustus) in the Battle of Actium. The book's assumption is that thereupon Antony and Cleopatra established the centre of their power in the city of Byzantium, which thus became an Imperial capital several hundred years earlier than in our history.
In practice, the Empire depicted in the book is quite similar to the Byzantine Empire of our history, except that it is Pagan and Christianity has never appeared, or at least never gained importance.