Un rasgo recurrente de las obras de Ficción de Kim Newman es su interés por reinterpretar figuras literarias, históricas y del cine, o introducir personajes de otros autores en nuevos escenarios, bien de historia alternativa realista o fantástica. Algunos de estos personajes, como por ejemplo el conde Drácula, son fácilmente reconocibles. Muchos más, especialmente personajes menores, son deliberadamente oscurecidos y pueden considerarse "huevos sorpresa" para los lectores perceptivos. Un ejemplo de ello es la aparición del estadounidense John Reid, que es propietario de una mina de plata y exporta balas de plata a Gran Bretaña en Anno Dracula. O la aparición de un actor estadounidense llamado Kent que protagonizaría "Hércules" en una producción italiana del mismo nombre (un guiño aparente a George Reeves y Steve Reeves (sin relación) que interpretaron a Supermán y Hércules respectivamente. (Aparecen en la novela Judgment of Tears: Anno Dracula 1959 y Dracula Cha Cha Cha.)
La primera novela de Kim Newman fue The Night Mayor (1989), ambientada en una realidad alternativa basada en las películas de detectives en blanco y negro. Ese mismo año y bajo el seudónimo de "Jack Yeovil" comenzó a contribuir a una serie de novelas publicadas por Games Workshop, ambientadas en su mundo de Warhammer y Dark Future y juegos de rol. Los libros de Dark Future fueron reimpresos en el 2006, publicándose Demon Download, Krokodil Tears y una versión extendida de 250 páginas del relato corto Route 666. Kim Newman no tiene previsto concluir la serie.
Su novela más famosa es Anno Dracula (1992). Ambientada en 1888, durante los asesinatos de Jack el Destripador, presenta un mundo alternativo, en el que el conde Drácula se ha convertido en el gobernante de Gran Bretaña. En la novela no sólo aparecen los personajes ficticios de Drácula (1897), sino también los de otras obras de la época victoriana y de sus novelas de Warhammer en otro escenario (aunque Newman ha aclarado que existen tres versiones alternativas de su heroína Geneviève: la versión de Warhammer, la versión de Anno Dracula, y la versión del Diogenes Club, que aparece en las Seven Stars, una colección de historias relacionadas y The Secret Files of the Diogenes Club.)
Anno Dracula fue continuada por una serie de novelas como El sanguinario barón rojo (ambientada en la Primera Guerra Mundial) y Judgment of Tears: Anno Dracula 1959, así como varios relatos cortos. Algunos de estos relatos están disponibles en la página en línea del autor.
Otras novelas suyas son Life's Lottery (1999), en la que la vida del protagonista es determinada por las elecciones del lector y una versión adulta de los libro-juegos The Quorum (1994), Jago (1991), and Bad Dreams (1990).
También escribió una novela sobre el Doctor Who, Time an Relative, publicada por Telos en el año 2001.
Kim Newman es un prolífico escritor de relatos cortos. Su primera historia fue Dreamers, que apareció en la revista Interzone en 1982. Entre sus colecciones de relatos cortos se incluyen: The Original Dr. Shade, and Other Stories (1994), Famous Monsters (1995), Seven Stars (2000), Where the Bodies are Buried (2000), Unforgivable Stories (2000), The Man from the Diogenes Club (2006) y The Secret Files of the Diogenes Club (2007). También se ha publicado Back in the USSA (1997), una colección de historias coescrita con Eugene Byrne, ambientadas en una historia alternativa en la que Estados Unidos sufrió una revolución comunista a comienzos del siglo XX y Rusia no.
Muchas de sus historias, especialmente las publicadas en Seven Stars, The Man from the Diogenes Club y The Secret Files of the Diogenes Club—muestran a los agentes del Club Diógenes, creado por Arthur Conan Doyle para la historia de Sherlock Holmes: La aventura del intérprete griego. En las historias de Newman se trata de una fachada para una organización secreta del gobierno británico dedicada a resolver los misterios y amenazas más allá del ámbito de la policía y el servicio secreto convencional.
Una parte de estos relatos se enfocan en las aventuras durante la década de 1970 del investigador psíquico Richard Jeperson; las historias homenajean varios aspectos de la cultura británica de la época, con aventuras al estilo de series de televisión como Los vengadores y Department S. Una versión del Club Diógenes también aparece en la saga de El año de Drácula, con una versión alternativa de Jeperson. Por otra parte, en la serie del Club Diógenes aparecen en ocasiones versiones alternativas de los personajes de la saga de El año de Drácula.
El relato corto Famous Monsters en la que un marciano que deja la invasión de La guerra de los mundos de H. G. Wells consigue un trabajo en Hollywood, fue incluido en una cápsula de información enviada a Marte en un operación conjunta ruso-estadounidense en 1994.