A man named Otto Rotfeld wants a wife. This is 1899, so he can't go on OKCupid. Instead, he visits a man named Yehudah Schaalman, and has a Golem made: a clay person who looks and acts human. She'll follow orders, unless she goes nuts and starts destroying things. Rotfeld and his newly made wife travel to New York City, but Rotfeld dies along the way, and the Golem has to set out on her own.
Meanwhile, in the Little Syria neighborhood of New York City, a tinsmith named Boutrous Arbeely is repairing a copper flask when—boom—a naked man shoots out of it. Where can we get one of those? The man is a jinni, and he's been trapped in that flask for a thousand years, put there by an evil wizard, but he's lost most of his memories.
The Golem meets a nice old Rabbi, Avram Meyer, who helps her get a job and learn the city. However, the Rabbi knows she's a Golem, and wonders if he should destroy her. He decides not to, but creates a spell to bind her to a new master, just to be safe. He dies of a heart attack before he can cast the spell, though. Then the Golem finds the spell to destroy her, and she keeps it—a girl never knows when she might need to self-destruct. All the rest of the Rabbi's work goes to his nephew, Michael.
The Jinni seduces Sophia Winston, a well-to-do young woman, and never calls, writes, or texts her again. She is eighteen and pregnant, but she miscarries his half-jinni baby.
One night, the Golem and the Jinni meet. Both of them are fascinated with the other, and they decide to develop a friendship, walking around New York at night, and seeing the sights, like the aquarium and Central Park.
At the Radzin's bakery, where the Golem works, the Golem makes friends with Anna, the clerk, and they go out dancing. The Golem invites the Jinni and they wow everyone with their dancing skills like it's Footloose or something. However, when Anna's loser baby daddy, Irving, hits Anna in an alleyway, the Golem loses her cool and attacks Irving, almost killing him. The Jinni takes her away. He finds the destruction spell in her locket and takes it.
When the Golem wakes up, she's wracked with guilt, and tries to destroy herself, but she can't without the spell. She decides to go to Michael, the Rabbi's nephew, and marry him, hoping that being his wife can help her regain her self-control.
While all this is happening, Yehudah Schaalman emigrates to the U.S. and is renamed Joseph Schall. He works at the Sheltering House with Michael by day, and is a total creeper by night, casting spells and searching for eternal life. Along the way, he kills Michael, the Golem's husband, who has just found out that his wife is a Golem and left her (fifty percent of marriages to golems end in divorce, the other fifty percent in death).
Schall's spells eventually lead him to the Jinni, and when they touch, sparks fly. Not in a romantic sense, but literall—a freaking building explodes, and they both regain their memories: Schall is the reincarnation of the evil wizard who captured the Jinni.
Meanwhile, the ice cream maker Mahmoud Saleh wonders why he, too, can see the Jinni. Turns out he was possessed by an ifrit and Schall inadvertently cures him while trying to find the Jinni. For some reason, Saleh decides to follow the Jinni around and help him. The Jinni also befriends a young boy, Matthew, and makes him his apprentice when Matthew's mother dies. Matthew helps the Jinni as he crafts works of art for Arbeely, like a fancy tin ceiling and gorgeous jewelry. (They need an Etsy page.)
The Jinni doesn't want to be enslaved again, so he tries to kill himself by drowning in a fountain in Central Park. The Golem rescues him, though, and they decide to take down the wizard together. Saleh follows them to the dance hall, where the wizard uses the master spell to bind the Golem to himself and orders her to trap the Jinni back in the flask.
Before she can, Saleh casts the spell and puts the wizard in the flask. Sadly, the Golem kills the old man in the scuffle, because she is still under the wizard's control. Once he's trapped, both her own and the Jinni's free will returns.
The Jinni takes the wizard-filled flask to the Syrian Desert, where he's from, to leave it in the protection of other jinnis. He drops off young Matthew with his grandmother along the way. While the Jinni is in the desert, he builds a tomb over the remains of Fadwa, a girl he was careless with a thousand years ago, resulting in her death and his imprisonment in the flask. He decides to return to New York City where his friend, the Golem is waiting.