Saylor's best-known work is his Roma Sub Rosa historical mystery series, set in ancient Rome. The novels' hero is a detective named Gordianus the Finder, active during the time of Sulla, Cicero, Julius Caesar, and Cleopatra. Outside this crime novel series, Saylor has also written two epic-length historical novels about the city of Rome, Roma and Empire. His work has been published in 21 languages.
Saylor has also written two novels set in Texas. A Twist at the End, featuring O. Henry, is set in Austin in the 1880s and based on real-life serial murders and trials (the case of the so-called Servant Girl Annihilator). Have You Seen Dawn? is a contemporary thriller set in a fictional Texas town, Amethyst, based on Saylor's hometown, Goldthwaite, Texas.
Saylor contributed autobiographical essays to three anthologies of gay writing edited by John Preston, Hometowns, A Member of the Family, and Friends and Lovers, and prior to his novel-writing career he published gay erotic fiction under the pen name Aaron Travis.
Saylor has lived with Richard Solomon since 1976; they registered as domestic partners in San Francisco in 1991 and later dissolved that partnership in order to legally marry in October 2008. The couple split their time between properties in Berkeley, California, and Austin, Texas.
- Roman Blood (1991), in which Gordianus is hired by the great orator and advocate Cicero in 80 BC. Like several novels in the series, this one is based on a trial oration by Cicero, in this case In Defence of Sextus Roscius of Ameria (Pro Sexto Roscio Amerino).
- The House of the Vestals (1997), a collection of short stories which take place between the first novel and the second.
- A Gladiator Dies Only Once (2005), another collection of short stories which take place between the first novel and the second.
- Arms of Nemesis (1992), featuring Crassus, is set during the slave revolt of Spartacus in 72 BC.
- Catilina's Riddle (1993), featuring Cicero and the title character, Catilina, is set during his rebellion in 63 BC.
- The Venus Throw (1995), featuring the poet Catullus, is set during the trial of Marcus Caelius in 56 BC for the murder of Dio of Alexandria.
- A Murder on the Appian Way (1996), set just before the civil war between Caesar and Pompey, focused on the murder of the rabble-rouser Publius Clodius Pulcher on the Appian Way outside Rome.
- Rubicon (1999), in which Caesar crosses the Rubicon and the members of the Senate flee Rome, plunging the Roman world into civil war.
- Last Seen in Massilia (2000) takes place in Massilia (now Marseille) during the siege of the city by Caesar's troops.
- A Mist of Prophecies (2002) is set in the city of Rome during the Roman civil war.
- The Judgment of Caesar (2004) takes place in Egypt, when Caesar met queen Cleopatra in 48 BC.
- The Triumph of Caesar (2008) is set in Rome during Caesar's triumphal celebrations in 46 BC.
- The Seven Wonders (2012), a fix-up novel, is a prequel recounting the journey of the young Gordianus to see the Seven Wonders of the Ancient World beginning in 92 BC.
- Raiders of the Nile (2014) is a direct sequel to The Seven Wonders, about the further adventures of young Gordianus in Egypt and a plot to steal the golden sarcophagus of Alexander the Great.
- Roma: The Novel of Ancient Rome (2007), a 1000-year novel of the rise of ancient Rome from its first settlement to the assassination of Julius Caesar.
- Empire: The Novel of Imperial Rome (2010) spans several generations with the end of the reign of Augustus in 14 AD through the reign of Hadrian in 141 AD.
Published under his own name:
- A Twist at the End (UK title: Honour the Dead) (2000), based on the Servant Girl Annihilator killings in the 1880s in Austin, Texas, closely reconstructs the murders and the ensuing trials, with young William Sydney Porter (O. Henry) playing a fictional role.
- Have You Seen Dawn? (2003) is a modern-day thriller set in a small town in Texas.
- Future, Present, Past (2013) is a collection of three short stories set in different time periods.
- My Mother's Ghost (2013) is a collection of three autobiographical essays and a short story.
- A Bookish Bent (2013) is a collection of various essay and articles.
- "Death by Eros" (1998), in the historical mystery anthology Past Poisons: An Ellis Peters Memorial Anthology of Historical Crime, edited by Maxim Jakubowski
- "The Eagle and the Rabbit" (2010), in the cross-genre anthology Warriors, edited by George R. R. Martin and Gardner Dozois
- "Styx and Stones" (2011), in the urban fantasy anthology Down These Strange Streets, edited by George R. R. Martin and Gardner Dozois
- “Ill Seen in Tyre” (2014), in the cross-genre anthology Rogues, edited by George R. R. Martin and Gardner Dozois
- Rapp, Linda (2005), Saylor, Steven, glbtq.com.