Over the course of one night, A Horse Walks Into a Bar follows Dovaleh Greenstein's stand-up performance at a small dive in Netanya. The book is not divided into chapters, but rather is one long passage that mirrors the long and often painful endurance required to sit through the comedian's performance. The novel is only broken up with gaps in the text, with most of the gaps separating narration of Dovaleh's stand-up with the narrator's memories of his interactions with Dovaleh before that night. Dovaleh's own stand-up comprises a significant portion of the novel, especially as he delves deeper into childhood stories later on.

The novel begins with Dovaleh cheekily greeting the audience as Caesarea, a neighboring city to Netanya. Dovaleh follows the routine of most comedians, establishing a rapport with the audience by teasing guests' fashions, nicknaming them after prominent body parts, and describing the city as a hovel for criminals and body bags. He is described as scanning the audience for a particular guest, upon which the narrator announces he is the one Dovaleh is looking for.

As Dovaleh continues shocking his guests with targeted jokes and controversial jokes about Israel's conflict with Palestine and the Holocaust, the narrator makes his discomfort there known, avoiding Dovaleh's gaze when he can and keeping as minimal a profile while sharing fears Dovaleh will embarrass him in front of the audience. The narrator rarely uses names to refer to anybody, rather using pronouns for Dovaleh or referring to guests in the audience by their physical descriptions. Dovaleh reveals it is his birthday today, which leads to him sharing the first of many stories from his childhood.

While Dovaleh performs his stand-up, he keeps sharing looks with the narrator. The novel then flashes back to the phone conversation the two had a few weeks prior to the night Dovaleh asked if the narrator remembered him, and the narrator struggled but eventually recalled a young, slight boy he attended remedial math classes with. Dovaleh asked if the narrator would come to his performance to watch, take notes, and describe the man he sees. The narrator showed reluctance over the phone, even criticizing the art of comedy, but while staring at his dog he remembered his compassionate wife who recently passed away.

During the first part of Dovaleh's performance, the narrator frequently prepares to leave, at one point asking for the check from a waitress for a meal he has ordered. Dovaleh notices and introduces him as Avishai Lazar, district court judge, to the entire audience, and Avishai stays in his chair out of embarrassment.

In the club, Dovaleh shares childhood anecdotes of his stern, practical father who ran a barbershop and sold resewn secondhand clothes and his quiet, withdrawn mother who wore a schmette and sorted bullets at a weapon factory in Taas. As Dovaleh laces his storytelling with humorous barbs, he notices a small woman on her phone and calls her out. The woman reveals she is taking notes, that she is a medium named Azulai from a nearby village, and she remembers Dovaleh from childhood. She rebukes his harsh jokes and cutting characterizations of himself and other people, saying that he had been a "nice boy," the only child who treated her well. Azulai's contradictions to Dovaleh's stand-up undermines his authority over the crowd, some of whom begin to rebel as Dovaleh begins telling more stories than jokes.

In response, Dovaleh resorts to more violent slapstick and crude jokes about Palestine to keep his audience's attention, but once the audience calms down he dives back into his story again. While Dovaleh shares more about his mother, a woman whom he idolizes, Avishai is reminded of his wife Tamara. As a judge, Avishai strived to be stoic and immovable while hearing cases, dealing out poetic rulings that his wife would edit beforehand. Tamara pushed him to show more compassion in certain cases, such as toward a daughter physically abused by her father. After Tamara's passing, Avishai became more emotional and temperamental during his proceedings, which led to his forced early retirement. As the judge watches Dovaleh in the present, he eventually realizes why the comedian seems so thin and ragged; he is suffering from cancer.

As Dovaleh struggles to keep his audience in their seats for his childhood stories, Avishai orders plentiful food to keep his energy up. Dovaleh describes how he used to walk on his hands to throw off bullies until a man in a yellow jacket and another man with thick shoulders begin heckling Dovaleh, ordering him to quit sharing his story and tell jokes like they paid for. Dovaleh entices them with various jokes he knows, including one about a foulmouthed parrot and another about a mortician pleasing a grieving family's funereal wishes, but every time he returns to his childhood the audience loses more patience. At one point, the audience erupts into a clamor as guests argue whether to let Dovaleh tell his story or make him tell jokes until Avishai, summoning his authoritative voice, commands the room to let Dovaleh tell his story. Dovaleh shoots him a look of gratitude.

Dovaleh's recountings of his parents hint that they were both immigrants to Israel, having escaped the Holocaust. Dovaleh's mother in particular endured a traumatic escape that left her scarred and unable to communicate well. His father loved his mother fiercely, although they differed in their treatment of Dovaleh. Dovaleh's mother was softer and more encouraging while his father punished him, often through beatings, for his odd behavior. Avishai recalls that when he and Dovaleh would meet after math classes, Dovaleh pried the normally stern Avishai open by describing his parents and asking Avishai about his, leading Avishai to open up about his and his family's travels between Paris, New York, and other cities around the world, and the two almost developed a friendship. They both met again when they attended a camp for adolescents in Be'er Ora. In the present, Dovaleh describes his fellow campers as lighthearted pranksters, but Avishai recalls that they brutally bullied Dovaleh, at one point trapping him in a bag and passing him around like a ball. Rather than standing up for him, Avishai distanced himself from Dovaleh, not wishing to be another victim of the bullies. In the present, Avishai fears Dovaleh will reveal they had both been at the camp to the audience.

Avishai remembers taking on guard duties and getting paired with a girl, his first love and kiss. The narrator realizes that he was able to get close to the girl by asking her questions and encouraging her to open up, something taught to him by Dovaleh. Avishai expresses regret for how he later rejected then forgot about Dovaleh as Dovaleh tells the audience how the camp's sergeants called him up and told him he had to leave the camp. Watched by the entire camp including his bullies and Avishai, Dovaleh was frightened by the sergeants' kind treatment toward him, having subjected him to boot camp punishments earlier for his erratic mannerisms. The young Dovaleh climbed into a truck with a driver angry about having to take him all the way to Jerusalem. The driver later felt remorseful and started telling Dovaleh jokes, many of them the same ones he has told the audience in the present.

Dovaleh tries to recapture his audience with more eviscerating jokes, and everyone laughs except for Azulai, who is disappointed how cruel the boy she remembers has become. Every time he tells a joke, Dovaleh returns to his childhood tale, slowly losing focus on his jokes. The man in the yellow jacket storms out of the club, dragging his wife with him. His departure is little noted by Dovaleh, but the crowd takes note. After Dovaleh shares about his father's obsession with collecting old clothes to resell, he lingers in silence too long. When he resumes his story, the crowd erupts. Most of the guests leave, with the thick-shouldered man and his wife complaining about Dovaleh's poor stand-up. Dovaleh hardly pays heed as more guests trickle out, leaving Avishai, Azulai, and a few others, including a young woman who stays after her friends leave and an older, silver-haired woman. They sit in rapt attention as Dovaleh finishes his story.

In the truck, the driver continued telling Dovaleh jokes as a way to prepare for a comedy contest the camp had nominated him for. Dovaleh is unresponsive, setting his head against the window as he tried to figure out what event had forced him away from camp. After the driver gave up, Dovaleh began thinking about his parents and realized he could not recall his mother as well as his father, which upset him as he favored her greatly. After wading through memories of his father teaching him about soccer or whipping him for walking on his hands, Dovaleh finally pictured his mother in her bathrobe, looking like Grace Kelly, sitting as he entertained her with goofy stories and gestures. She would laugh, one of the few times when Dovaleh got to see her smile. Dovaleh became too overwhelmed to think about his parents and asked the driver to tell him a joke. The driver's joke, more adult than his others, sent the young Dovaleh into fits of laughter.

The driver continued his jokes until Dovaleh fell asleep. They later stopped to pick up the driver's sister, holding a baby. When she climbed in, she scolded her brother for telling Dovaleh mean jokes and fed Dovaleh with a sandwich, cookie, and juice. As she fed him, she queried him about his life, and Dovaleh admitted out loud that his father and he got along better when his mother was present. On the way, Dovaleh vomited for the first time without his mother there. In the present, Dovaleh recalls how his mother would scream at night, which his earlier stories hint were due to post-traumatic stress disorder.

Returning to his story, Dovaleh shares how the driver, his sister, and Dovaleh arrived at Givat Shaul, where a funeral was being conducted. The driver and his sister parted from Dovaleh as a rabbi rushed Dovaleh into the building, placing a yarmulke onto his head. He came into a room where he found his father and various neighbors standing around a long, wrapped body. The rabbi told Dovaleh to ask for forgiveness, revealing that his mother had died. Dovaleh's father noticed him and hugged him fiercely, stricken with grief over their loss, but Dovaleh rejected his father's hug, leapt onto his hands, and hand-walked outside. Furious over Dovaleh's lack of respect, his father cursed him. In the present, Dovaleh expresses his belief that the curse to that day has caused his marriages to fail and his family to drift from him, leaving him to die alone.

In the club, after Dovaleh finishes his story, a young woman bursts into tears, and Avishai wonders if she is one of Dovaleh's daughters. The older woman before leaving puts a folded note on Avishai, presumably a number for him to call. The guests trickle out, and the club manager Yoav starts stacking up chairs. Only Dovaleh, Avishai, and Azulai are left. Dovaleh kisses Azulai softly on the lips, thanking her and calling her Pitz, and she leaves elated. Dovaleh and Avishai remain together, and Avishai feels his former wife's presence. They catch up briefly; Dovaleh reveals he felt his mother present in the club, as more than his mother but as a human being. and that he and his father stayed together, with Dovaleh taking care of the man in his dying days. Avishai offers to take Dovaleh home, and Dovaleh closes out the evening by wishing Ceasarea good night.