A year later, I had a story in my head about these people. I tried writing it: the character I’d thought of as a magician (although, I had already decided, he wasn’t a magician at all) now seemed to be called Wednesday. I wasn’t sure what the other guy’s name was, the bodyguard, so I called him Ryder, but that wasn’t quite right. I had a short story in mind about those two and some murders that occur in a small Midwestern town called Silverside. I wrote a page and gave up, mainly because they really didn’t seem to come together.

There was a dream I woke up from, somewhere back then, sweating and confused, about a dead wife. It seemed to belong to the story, and I filed it away.

Some months later, in September 1998, I tried writing that story again, as a first-person narrative, sending the guy I’d called Ryder (who I tried calling Ben Kobold this time, but that sent out quite the wrong set of signals) to the town (which I’d called Shelby, because Silverside seemed too exotic) on his own. I covered about ten pages, and then stopped. I still wasn’t comfortable with it.

By that point, I was coming to the conclusion that the story I wanted to tell in that particular little lakeside town . . . Hmm, I thought somewhere in there, Lakeside, that’s what it’s called, a solid, generic name for a town . . . was too much a part of the novel to be written in isolation from it. And I had a novel by then. I’d had it for several months.

Back in July 1998 I had gone to Iceland, on the way to Norway and Finland. It may have been the distance from America, or it may have been the lack of sleep involved in a trip to the land of the midnight sun, but suddenly, somewhere in Reykjavik the novel came into focus. Not the story of it—I still had nothing more than the meeting on the plane and a fragment of plot in a town by a lake—but for the first time I knew what it was about. I had a direction. I wrote a letter to my publisher telling them that my next book wouldn’t be a historical fantasy set in restoration London after all, but a contemporary American phantasmagoria. Tentatively, I suggested American Gods as a working title for it.

I kept naming my protagonist: there’s a magic to names, after all. I knew his name was descriptive. I tried calling him Lazy, but he didn’t seem to like that, and I called him Jack and he didn’t like that any better. I took to trying every name I ran into on him for size, and he looked back at me from somewhere in my head unimpressed every time. It was like trying to name Rumpelstiltskin.

He finally got his name from an Elvis Costello song (it’s on Bespoke Songs, Lost Dogs, Detours and Rendezvous). It’s performed by Was (Not Was) and is the story of two men named Shadow and Jimmy. I thought about it, tried it on for size . . . and Shadow stretched uncomfortably on his prison cot, and glanced across at the Wild Birds of North America wall calendar, with the days he’d been inside crossed off, and he counted the days until he got out.