Paul Evanby's stories first appeared in 1985, in the Ganymedes anthologies from Dutch publishers A.W. Bruna & Zn. In 1988 he was awarded the Millennium Prize (later: Paul Harland Prize) for best short science fiction — the youngest author ever to have done so. Since then he has produced a small body of work, which has been published in a variety of anthologies, collections and magazines, such as for example Babel Publications' Ragnarok I to IV, Verschijnsel's Zwartboeken, Holland SF, Waen Sinne, and more.
The year 1995 saw the publication of Systems of Romance, an English-language collection containing stories by him and the late Paul Harland, which received critical acclaim in the UK. In the words of Andy Sawyer from the Science Fiction Foundation: ‘This is confident writing which neither proclaims a “national tradition” nor echoes that of others, but connects with a whole range of romantically imaginative storytelling.’ In 2001 he won the Millennium Prize for a second time, and in 2003 the collection Gödel Slam appeared from Babel, containing eleven of his best stories.
In the UK and the US his work has appeared in, for instance, Interzone, Harrington Gay Men's Literary Quarterly, Nemonymous and the themed anthology The Elastic Book of Numbers, which won the 2006 British Fantasy Award for Best Anthology.
His first novel, De scrypturist, appeared from Meulenhoff Boekerij publishers in September 2009. This book, which caused a stir thanks to its richly imagined and original setting, was followed by his second, De vloedvormer, in November 2010.
His latest book, Een rivier van goden, set in a reimagined Bronze-Age Mesopotamia, appeared in 2013.