Mary “Mississippi” Brown is a resourceful, self-sufficient southern gal who has been dealt a bad turn in life. Quick-witted and beautiful, most men could be her playthings and most are…except for Cheyenne Bodie.
With the defeat of the Confederacy looming near, Mississippi and her doctor father decide to emigrate to Brazil with a group of southerners eager to carry on their way of life. The trip turns tragic when their boat sinks, stranding the survivors in Panama. Her father ailing, Mississippi tries to support them both using any methods she can: singing in cantinas, playing cards and other ways that she’s not proud of. After six months, her father passes away and Mississippi travels north through Central America, hoping to get back to her home state of Mississippi.
Mississippi manages to scrape together stagecoach fare and makes it to Rio Hondo. During the trip, a business man named Bolados takes a liking to her. At dinner that night in the hotel cantina, Mississippi takes a liking to Bolados’ wallet and slips away to her room. But before she can escape she’s confronted in the hallway by a tall cowboy who demands she give up the wallet. The cowboy is Cheyenne Bodie, and Bolados owes him money.
Their conversation is interrupted by Manuel the cantina owner, Mexican rebels who want Cheyenne’s help moving sensitive cargo, and Cheyenne’s partner, the elderly Pete. Mississippi enjoys Pete’s quirks, and takes special notice of Cheyenne’s gentle treatment of the old timer.Biding the others goodbye, Mississippi goes with Bodie back to the dining room to confess her crime to Bolados. French soldiers appear and fire on a trio of Mexican rebels, sending stray bullets into the crowd. Cheyenne pulls Mississippi down to the floor in time, but Bolados isn’t as lucky.
An investigation into the shooting ensues, bringing Mississippi and Cheyenne to the attention of French officer Colonel Picard, commander of Rio Hondo. Bodie cuts the interrogation short by unintentionally buying their freedom with the money from Bolados’ wallet.
Broke and hungry, Mississippi bets Cheyenne she can get a dinner out of someone in a local cantina and the cowboy leaves her to it, to her dismay. Alone now, she wanders the streets for a time then returns to the hotel where she finds Cheyenne finishing dinner. She shares the story of her recent misfortune, the passing of her father and her journey home. She tries to get Bodie around her finger, but he resists all of her tricks.Mississippi later visits Cheyenne in his room and tells him she suspects he's going to take a dangerous job transporting one of the leaders of the Mexican rebels to get money to help her. Bodie confirms this and she begs him not to do it, offering him the last thing of value she has -- her mother's earrings. He refuses to take them. She gives him a kiss, hoping to weaken his resolve, but Bodie kisses her back and still refuses. Mississippi backs away when he moves in for another kiss and bids him goodnight.
The next day, she meets with Cheyenne again and the cowboy is angry. He paid Manuel to get Mississippi on the stage, but she refused to leave and instead asked the cantina owner for a job as a singer. Mississippi looks on as Manuel begs Cheyenne to help the rebels again by removing a bullet from the rebel leader who was shot during the trip in Bodie's wagon. Mississippi volunteers to help and offers one of her father's forceps to Cheyenne for the operation.
In the evening, Mississippi performs for the crowd in the cantina with the cantina's piano player, the Professor, and after Cheyenne invites her to come to the States with him. She agrees this time. But before they can leave, Picard and his soldiers return to the hotel. The colonel heads straight for Cheyenne's room who is in an impromptu meeting with the rebel leader's wife. Mississippi takes the woman out to hide on the balcony while Cheyenne tries to stall the soldiers.Picard enters, smells the lingering scent of the wife's perfume and suspects a female presence, so Mississippi steps back into the room holding the wife's shall in her hand. Picard reveals that he has imprisoned Pete and will torture the old man by using his fear of fire against him unless Bodie cooperates. Mississippi pulls the shall away, revealing a pistol. Cheyenne takes the gun and flips the situation around, taking Picard prisoner. He tells Mississippi to go downstairs and get the Professor to play loudly to cover the sound of the gunshot he plans to put in the colonel. Mississippi smiles vengefully and says she'll sing along. Afraid for his own life, Picard relents and signs the paperwork to give the rebels safe passage to the United States.
Packed and in traveling clothes, Cheyenne and Mississippi say goodbye to Manuel and the Professor. As the pair exits the cantina, the Professor serenades them by playing "Dixie".