In 1962 in New York City, Tony "Tony Lip" Vallelonga (Viggo Mortensen) is a doorman and peacekeeper/bouncer at the Copacabana nightclub. He's known as Tony Lip because he's an amazing "bullshitter" - getting people to do what they don't want to. He does what he has to to put food on his family's table. When two men start getting into a fist fight, he tosses one out onto the street and gives him a few punches in the face when he resists. He pays the coat check girl to take a rich patron's prized hat so he can "find" it and return it to him for a very big tip.
The club closes for a few months for renovations, leaving Tony out of work. He and his wife, Dolores (Linda Cardellini), are having trouble making the rent and keeping a roof over their two kids' home. When two black men come over to repair the sink, Dolores gives them lemonade - and Tony throws out their glasses after they use them, much to Dolores's disappointment. Tony makes fifty bucks in a hot dog eating contest to make ends meet. An old contact gets him an interview to be a driver for a doctor, and he goes to Carnegie Hall for the interview. He mistakenly goes to the venue, but learns there's an apartment upstairs. It's ornate and filled with objects around the world. Dr. Don Shirley (Mahershala Ali). He's not a medical doctor, but a concert pianist. He's doing a concert tour going from the Midwest into the deep south, and needs a driver, but he asked around specifically for someone who could handle trouble - he knows there's going to be racism against him. The tour is two months long, and ends right before Christmas. He asks Tony if he can be away from his family that long, and Tony agrees for the right money. But when Don insists that Tony be prepared to iron his clothes and shine his shoes, Tony refuses, saying he's not a butler. Don dismisses him.
Tony goes to a bar, upset he fumbled the interview, and a couple of mobsters he knows from the club offer him unsavory work. He declines, lying that he's got money saved. Early the next morning, Don calls Tony's house and asks to speak to Dolores. He asks her if she's okay with her husband being gone for so long. When she agrees, he offers Tony the job. Dolores asks Tony to write her letters, much to his chagrin. The record company rents Tony a nice car, and gives him half the money up front, and tells him he'll get half at the end of the tour - if Don misses a show, he won't get the money. They also give him the 'Green Book', a tourist guide and list of safe places for black people to stay in the segregated Jim Crow southern states.
Tony is a loudmouth and a talker, and gets on Don's nerves a lot during the drive. As they approach their first tour stop, Don suggests that Tony use a different last name and try to talk better around the guests, but Tony says if they have a problem with how he talks, he'll wait outside, which he does. From outside he watches Don play piano and is impressed with how brilliant he is. Afterwards, he gambles with the other help who are all also outside, and Don is upset with him for being so low-class. Tony wants to know why Don is giving him such a hard time and no one else - and Don says it's because unlike the other help, Tony had the option of being inside.
In the car, Tony plays contemporary music on the radio and is shocked when Don doesn't know popular music like Aretha Franklin. He questions if Dr. Don Shirley is even black, and when he drives by a Kentucky Fried Chicken and finds out Don has never had fried chicken, he stops. He playfully forces Dr. Shirley to try the chicken. Tony works on his letters for Dolores, and they're terrible, so Don helps him make them more poetic and beautiful. At a later stop, Tony finds a gemstone that's being sold on the ground and pockets it, but Don forces him to put it back, saying it's stealing even though Tony disagrees.
As they enter the south, Don has to stay at blacks only hotels separate from Tony. Alone, Don drinks by himself, alienated from the other people at the hotel. Tony gets a call at his room that there's a skirmish happening at a local bar, where he finds Don being assaulted by racist white patrons. Tony reaches for a gun and claims he'll shoot if they don't let him go. They narrowly escape, and Don asks if he really has a gun. Tony says of course not, and orders Don to go nowhere without him.
At the next concert venue at a Southern mansion, the host is very friendly to Don. For dinner he has had the cooks prepared fried chicken. At intermission, Don asks to use the bathroom, and the host directs him to the outhouse, not allowing him to use the inside bathroom. Don refuses to use the outhouse, so Tony drives him back to his hotel just to use the bathroom there.
At the next stop, the two walk by a suit store, and when Don admires a suit in the window, Joe insists he buy it. When they enter the store, the racist employees refuse to sell Don a suit. That evening, Tony is called to a disturbance at a local YMCA where Don and another local white man have been arrested - apparently the gym manager caught them in a fistfight. Tony bribes the police officers to let Don go.
At the next town, Tony runs into the mobsters. In Italian, in front of Don, they tell Tony that he should quit and come work for them. Tony agrees to meet them for a drink later that night. As they check into their hotel, Don offers Tony a raise and a promotion. Tony refuses to accept, and Don reveals he speaks Italian. Tony explains he was never going to take the job, he was going to meet them and tell them now. Don is relieved. He awkwardly apologizes to Tony for the situation the night before, but Tony explains that he's been working in New York City nightclubs for years and knows that the world is "complicated".
Don continues to help Tony with writing the letters, which continue to impress Dolores and the rest of his family. On the way to their final stop, they are pulled over by the local police. The redneck officer tells them that Don can't be out past sundown (in part due to the town they are in being a Sundown Town... where all black people are under curfew). They are both forced out of the car and frisked, and the officer asks Tony for his ID, who shows the officer his New York driver's license. When the officer asks Tony what kind of last name Vallelonga is, Tony says it's Italian... and the racist officer insults Tony by calling him "half a nigger". Tony immediately punches the redneck officer in the face, and both him and Don are arrested and taken to jail.
In their cell, Don is enraged at Tony, since his hot head cost them the tour. Don demands to make a phone call, since he committed no crime. The police allow him to. A short while later, the police receive an angry call from the Governor and reluctantly release both Tony and Don. Don reveals to Tony that he called the US Attorney General Robert Kennedy. Tony thinks that's amazing, but Don is furious. He is embarrassed that someone so important now sees him as a rabble-rouser. The two men have a huge argument over all their differences - Don sees Tony as a man who refuses to better himself, and Tony sees Don as a man who seems to make things more difficult for himself and fits in nowhere. Don screams at Tony, "if I'm not black enough, and I'm not white enough, I'm not man enough, then what am I?"
The two arrive at the final concert venue at another hotel, where Don is shown to a tiny closet that they refer to as his dressing room. Tony goes to eat in the dining room with the players in the band, but when Don arrives to join them, the concierge refuses to let him eat there. Don refuses to play unless he is able to eat in the dining room. The concierge won't allow it, and Tony pulls him aside to talk to him. Tony tries to reason with him, but the concierge tries to bribe him to get Don to play. Don enters, and tells Tony he'll do the show if Tony wants, knowing Tony won't get paid unless they finish the tour. But Tony sticks with Don, and they bail on the gig despite the screams of the concierge.
They go down the street to a bar for black people. Don buys a round of drinks, flashing his wallet filled with money, which a couple of black youths see. After some prodding, Don plays piano with the jazz band. When they leave, Tony spots the two youths waiting behind their car to mug them, and fires two shots off into the air to scare them away... revealing he did have a gun all along.
Tony and Don begin their drive back to New York, hoping to make it by Christmas Eve. The weather is really bad, with a lot of snow. They get pulled over again, but this time the cop just warns them their tire is skidding. Tony can't stay awake any longer and can barely see through the snow, and accepts he won't make it home and goes to sleep - but while he sleeps Don drives them the rest of the way to Tony's apartment. He wakes Tony up and encourages him to go home - Tony invites him but he declines. Tony goes upstairs and surprises his family. Don returns to his ornate apartment, and sits there alone. He ends up coming to Tony's, and while most of his family is a little confused, Dolores joyously welcomes him and thanks him for helping Tony with his letters.
The post-script reveals that in real life, Tony became the maitre'D of the Copa, and Dr. Shirley continued being successful in music. They remained friends for the rest of their lives.