New York City bouncer Frank "Tony Lip" Vallelonga is searching for new employment while the Copacabana nightclub, where he works, is closed for renovations. He is invited to an interview with Doctor Don Shirley, an eccentric African American pianist who is looking for a driver for his eight-week concert tour through the Midwest and Deep South. Don hires Tony on the strength of his references and with the agreement of his wife, Dolores. They depart with plans to return to New York on Christmas Eve. Don's record label representatives give Tony a copy of the Green Book, a guide for African-American travelers to find motels, restaurants, and filling stations that would serve them.
They begin the tour in the Midwest before eventually heading farther south. Tony and Don initially clash, as Don is disgusted by Tony's habits while Tony resents being asked to act with more refinement. As the tour progresses, Tony is impressed with Don's talent on the piano, and increasingly appalled by the discriminatory treatment that Don receives from his hosts and the general public when he is not on stage. A group of white men threaten Don's life in a bar, and Tony is alerted and rescues him. He instructs Don not to go out without him for the rest of the tour.
Throughout the journey, Don helps Tony write love letters to his wife, correctly spelling, dictating, and rephrasing passages which deeply move her. Tony encourages Don to get in touch with his own estranged brother, but Don is hesitant, observing that he has become isolated by his professional life and achievements. In the south, Don is detained by police officers during a gay encounter with a white man at a YMCA pool, and Tony bribes the officers to prevent the musician's arrest. Don is upset that Tony "rewarded" the officers for their treatment. Later, the two are arrested after a police officer pulls them over late at night in a sundown town, and Tony punches him after being insulted. While they are incarcerated, Don asks to call his lawyer and instead uses the opportunity to reach Attorney General Robert F. Kennedy, who pressures the governor into releasing them. Because Tony lost his temper, Don is frustrated that he had to distract Kennedy who, with his brother President John F. Kennedy, are working hard for minority rights.
On the night of the final performance on tour in Birmingham, Alabama, Don is refused entry into the whites-only dining room of the country club, the same room in which he has been hired to perform and where many of his audience members are eating. He can order from the menu but must eat in a cramped pantry (which is also used as a changing room). First Tony says to Don that it is the last show, and he should order from the menu so they can finish and go North. Don says he will not perform at the country club unless he can eat in the dining room. The owner tries to bribe Tony into talking Don into performing, and Tony prepares to assault him. Don calms Tony down, saying that he will let him decide whether he should play or not. Tony walks out, followed by Don, with the management yelling about the contract. Tony takes Don, still in white tie and tails, to get dinner at a predominantly black blues club, Orange Bird, where Don rouses the crowd with a passionate rendition of Frederic Chopin's Winter Wind etude before being joined by the very impressed blues band. He then plays and improvises as one of the band, which gets everyone on their feet dancing.
Tony and Don head north to try to make it home by Christmas Eve. While en route on a snowy road they are stopped by another police officer, and expect further police harassment. To their surprise, the officer turns out to be a Maryland State Trooper who has noticed they have a flat tire, and he helps Tony safely change it. Tony soon realizes he is too exhausted from driving in the snow to get home without sleep, and tells Don that he will stop at the next lodging. Later that night the car arrives in the snowy Bronx with Don driving and Tony asleep in the back. Don wakes Tony, and tells him he's home. Tony invites Don to come in and meet his wife, but Don wishes him a merry Christmas and drives away.
Don arrives back at his apartment above Carnegie Hall, and soon realizes that he is alone on Christmas Eve. Behind a late arriving couple, Don suddenly appears in the hallway at Tony's place with a bottle of champagne. Tony embraces Don, then introduces him to his guests. Dolores walks up and embraces Don and then, whispering in his ear, warmly thanks him for helping Tony with the letters.
The film postscripts read:
- "Dr. Shirley continued to tour, compose, and record to great acclaim. Igor Stravinsky said of him, 'His virtuosity is worthy of the Gods.'"
- "Frank 'Tony Lip' Vallelonga went back to his job at the Copacabana, eventually becoming maître d'"
- A real picture of Tony and Dolores at the Copa, circa 1960 is shown.
- "Tony Lip and Dr. Donald Shirley remained friends until they died within months of each other in 2013."