Paul Auster’s novels can mess with your head. His latest, Invisible, is set partly in Paris — back in 1967, when Saint-Germain was rather more run-down than it is now. Adam Walker, one of the book’s three narrators, holes up in a fleapit called the Hotel de Sud on the rue Mazarine. Now, my mother spent a lot of time in Paris in the 1950s and early 1960s; and long ago she gave me a heavy brass key fob that she had purloined from a hotel there. It had been hidden down at the bottom of a desk drawer somewhere when I started reading this novel — and as I read I became convinced that the fob was from, yes, the Hotel de Sud.

When Auster and I speak, he tells me that he’d be surprised if my memory was right. He stayed in the place back in 1965, two years before the novel was set. “It was such a dump, I can’t imagine they would have keyrings,” he says in his deep and appealing voice — which still carries a hint of his native New Jersey. Later, after a fair bit of searching, I found the fob — and discovered that he was right. It’s from the Hotel Solferino, on the rue de Lille. But it’s little wonder I was drawn in: Austerland is a place of strange, rich coincidences, where objects assume talismanic significance.

The last time we spoke was just after September 11, 2001, when a collection of stories he had edited, True Tales of American Life, had just been published. The book (which appeared in the US under the rather more wonderful title I Thought my Father was God) was a collection of true stories solicited by Auster as part of a project for National Public Radio; in the aftermath of the attacks on the twin towers, these often moving, sometimes eerie tales had a special resonance, and seemed to prove Auster’s theory that a life moved by coincidence and serendipity was not his lot alone.

Not for nothing is the title of one his novels The Music of Chance. Since then Auster, now 62, has published six novels — The Book of Illusions, Oracle Night, The Brooklyn Follies, Travels in the Scriptorium, Man in the Dark and now Invisible — all of which feature individuals who find themselves at extremes. His characters lose their families, their health or any sense of their own identity: they are left to remake the world in words, and it’s up to the reader to follow their stories — to choose to believe them or not. “Invisible,” Auster says to me, “is a word for what can’t be known.”

This novel is a departure for Auster, told as it is in three voices. There is Adam Walker, a young writer and an undergraduate at Columbia University in New York (as Auster was, at the time the novel is set) who gets caught up with the sinister and compelling Rudolf Born, a wealthy European who offers to fund a literary magazine that Walker will edit. There is Jim Freeman, a successful author and classmate of Walker’s, to whom Walker sends his as-yet-uncompleted memoir of his young manhood and his encounters with Born. And there is Cécile Juin, once nearly Born’s stepdaughter, who visits him in his later years when he has retreated to Kurtz-like isolation on a Caribbean island. It is a compelling book, a page-turner, and what you might call an existential mystery.

Auster’s fiction is always that of worlds-within-worlds: when Freeman receives Walker’s manuscript and reads it, he says: “If I hadn’t been told it was a true story, I probably would have plunged in and taken those 60-plus pages for the beginning of a novel (writers do, after all, sometimes inject characters who bear their own names into works of fiction) . . .”

The name Paul Auster has certainly appeared in his own books; but such effects (such as claiming the opening of a novel is a true story) don’t make the reader wonder whether his work is autobiographical: rather, they make her consider the nature of the stories we all tell all the time. Our lives are the stories we construct. There is, in this novel, a vivid and convincing description of an incestuous relationship between Walker and his sister Gwyn; there is a hint, too, that Born may have been responsible for the death of Juin’s father. Does Auster know more than his readers? Is he trying to trick us? “I feel that I don’t know more than the reader,” he says. “I feel very much in the position of the reader. I don’t know if Born killed Cécile’s father. I think probably not, in fact. But he’s somebody who might have thought about that. But I don’t know if he would have done it. Did the incest really happen or not? Jim thinks probably yes, it did: why would Adam have written it? But Gwyn’s denials seem so convincing. So you don’t know, you just don’t know.” He calls to mind a character from his previous novel, Man in the Dark: “Brill thinks to himself: the real and the imagined are one. Thoughts are real. Even thoughts of unreal things. And this is true.”

Such uncertainly arises from the stable base of a 30-year marriage to a fellow novelist, Siri Hustvedt. It would be fair to say that she started in his shadow — her first novel, The Blindfold, was published in 1992, when Auster had already found fame with his acclaimed “New York Trilogy”, City of Glass, Ghosts and The Locked Room — but has found her own acclaim, particularly for her two most recent novels, What I Loved and The Sorrows of an American.

“It’s good to be with someone who understands what you’re doing, and we have an endless conversation about each other’s work. We are the first reader for the other’s books. And I don’t think there’s a moment, a single instant, when I haven’t taken her advice about something. She’s always right. I don’t think she’s ever, ever been wrong about my work.”

Two writers living together, though — isn’t there a chance of rivalry? It’s clear that never comes into it. “We have a pact,” he tells me, “one of absolute honesty. I adore her work. I think she’s a brilliant, brilliant writer. I’m for it. And because you’re for the project, you have the freedom to point out weaknesses in the hope that this thing will become the best thing it possibly can on its own terms. This is what you might call — what did we call it in school? — constructive criticism.” He laughs his gravelly laugh.

The two share a townhouse in Brooklyn and have a 22-year-old daughter, Sophie, who is as beautiful as the bone structure of both her parents would suggest, and has already made her debut as a recording artist. Quite a household of artists, I say. “Oh, yes,” he says, “we sometimes call ourselves The Flying Wallendas.”

His books, it’s fair to say, have in recent years been better received in Europe than they have in his native land — he has an honorary doctorate from the University of Liège, and in 2006 won the Prince of Asturias Award for Literature, a kind of Spanish Nobel Prize. To some his work is a sustained investigation of recurrent themes; to others it’s repetitive. “I’ve trained myself not to read reviews,” he says, “so I really don’t follow what people say at all. But I can tell you that everywhere I get very enthusiastic responses — and very hostile ones. The whole range. But very little in between.”

He draws a distinction between books as entertainment and books as artistic endeavour: “People like to escape, and just go into a story,” he says. “People go to the movies or watch TV for the same reason. But then there are people who are interested in art. And it’s not just novels and poetry but painting, music — the whole history of art and literature. Those people read books in a much larger context than the people who just pluck a popular novel off the shelf and plunge in for a few hours of entertainment." Is the boundary between art and entertainment that clear? Not in Auster’s work, I’d say — I mean no disrespect. He calls writing “a strange, utterly mysterious process”; first there was nothing, he told me, and then suddenly: something. For the reader the experience is similar: his apparently ordinary, plain-spoken style conjures subtle wonders. Invisible magic, perfectly real.

Invisible is published by Faber and Faber on Nov 5, £16.99

Times Recommends

• The 100 Best Books of the Decade
• The Times picks the 50 best paperbacks of 2009
• The conversation: James Ellroy