After watching a movie, Captain Haddock rounds a corner and bumps into General Alcazar, who drops his wallet. Tintin attempts to return it, but the hotel he claimed to be staying at never heard of him, and when Tintin calls a phone number found in his wallet, the man refuses to talk to him. Tintin and Haddock later find Alcazar talking with Dawson at another hotel. Haddock returns the wallet, while Tintin follows Dawson and overhears him discussing how successful his sale of De Havilland Mosquitoes were in starting a coup d'état in Khemed. Tintin and Haddock decide to go there and rescue the emir.
At Wadesdah Airport they are turned back by customs, while someone plants a bomb on the plane to "take care of them". The bombing is foiled by an engine fire, which forces the plane to crash-land minutes before the bomb goes off. Tintin and Haddock walk away from the crash site to meet another old friend, who provides horses that they ride to where the Emir is staying. They are saved from attack by the Mosquitos by a garbled military order.
The Emir tells them about the ongoing slave trade run by the Marquis di Gorgonzola. Tintin and Haddock leave for the coast and board a boat for Mecca to investigate. They are attacked by the Mosquitos again, and shipwrecked along with Piotr Szut, the pilot of one of the planes that attacked them. They are then picked up by di Gorgonzola's yacht and offloaded the next night to the SS Ramona, a tramp steamer. Unbeknownst to Tintin and Haddock, the Ramona is one of di Gorgonzola's own ships, used in the slave trade.
That night they are locked into their cabin by Allan, Haddock's former first mate, while the Ramona's crew attempts to light fire to the ship. The prisoners force the door and manage to put out the fire, not realizing that the front of the ship was loaded by explosives. They then free a number of men from a rear hold who had paid for voyage to Mecca, but were intended to be sold as slaves instead. Haddock attempts to explain the situation to them (who speak Yoruba), but most of them don't understand, or refuse to, thinking Haddock is lying. After some discussion on their own they agree to help Haddock sail the ship to neutral territory in Djibouti, while Tintin and Skut attempt to fix the radios, which had been smashed.
Tintin finds a slip of paper in the radio room with an order to deliver "coke", and is puzzled. In shipping, "coke" would normally refer to a coal-based fuel, but none is being carried (this is prior to the use of "coke" to mean "cocaine"). They are then approached by a dhow and take aboard an Arab who wishes to inspect the coke, puzzling Haddock who claims they have none. The man then turns about and starts examining one of the Africans. With the nature of the term coke, a cover term for slaves, clear to them, Haddock throws him off the ship, and is saved by one of the Africans from the Arab's knife.
di Gorgonzola (who is actually the movie director Rastapopoulos from Cigars of the Pharaoh) finds out that Haddock has taken control of the ship from the Arab, and sends a submarine to attack them. Tintin spots the sub by accident just prior to attack. Haddock manages to outmanuver a number of torpedos, but all appears lost when the engine room telegraph gets stuck in full-reverse. At this point the Ramona is saved by the arrival of aircraft from a nearby US cruiser, who had been radioed by Skut. The submarine makes one more attempt to destroy the Ramona by attaching a limpet mine to the front of the boat beside the explosives, but this is foiled when the diver is hit by the Ramona's anchor being dropped. A shark swallows the mine and swims away. di Gorgonzola escapes, but Tintin, Haddock and Skut return to Europe for a hero's welcome.
The Red Sea Sharks has been criticised for its sterotypical portrayal of Africans, both in appearance and behaviour; although obviously good-hearted, the black characters are shown as being somewhat childish and simple. In the author's defence, Herge obviously had a real contempt for slavery, as evidenced by the scene in which Captain Haddock hurls obscenities at an Arab trying to buy a slave.