Around 900 BC, a Phoenician merchant ship sails to a remote and abandoned colony and conceals an unidentified treasure in a cave. On departing, they are approached by a more powerful Phoenician vessel. The first ship's captain, Menelik, meets on shore with the other ship's captain, his half-brother Melqart. Melqart ambushes Menelik and his men but they fend them off and destroy Melqart's ship.

In 1809, Thomas Jefferson prepares to return to Monticello at the end of his second term as president. A thief boards a river barge carrying his possessions with orders to destroy Jefferson's research on American Indian languages. However, some materials survive, including an unusual vellum with Phoenician writing Jefferson obtained from the Unkechaug tribe on Long Island. Jefferson believes the vellum reveals that the original tablets of the Ten Commandments were concealed in King Solomon's Mines in North America. Worried that the discovery will lead to unchecked westward expansion, he sends Louisiana Territory governor Merriwether Lewis a coded message concealed as an article about artichokes. Lewis dies under mysterious circumstances shortly after receiving the message.

Shortly after the U.S. invasion of Iraq, Italian-Ethiopian UNESCO investigator Carina Mechadi arrives at the Iraq Museum in Baghdad to investigate the looting of Iraqi antiquities in the chaos of the invasion. Senior curator Dr. Nasir tells her many items were looted by a group that had planned in advance to exploit the confusion. Dr. Mechadi meets with Iraqi antiquities smuggler Ali who she believes is responsible to seek the return of the items. After she leaves, professional assassin Adriano meets with Ali to discuss the purchase for businessman Viktor Baltazar of the Navigator, a bronze statue that shows an ancient Phoenician mariner using a compass. Ali tries to get more money from Adriano, who murders him to keep the statue from being sold to another buyer.

Baltazar anonymously provides Dr. Mechadi with unlimited funds for the recovery of Iraqi antiquities. Mechadi locates a cache of looted antiquities including the Navigator in Egypt. She purchases them with Baltazar's funds and places them on the container ship Ocean Adventure to the U.S. where she plans a museum tour to raise awareness on losses to Iraqi heritage. In the north Atlantic, Adriano and a party of mercenaries hijack the ship. After tying up Mechadi and the crew, they prepare to remove the Navigator by helicopter and set the ship's autopilot on a collision course with a nearby oil rig to eliminate evidence of their attack and kill witnesses. A Canadian International Ice Patrol ship picks up a distress call from the oil rig. National Underwater and Marine Agency employees Kurt Austin and Joe Zavala, who had been on the ice patrol ship to learn about iceberg wrangling, intervene. With Zavala's aid, Austin boards the container ship from a small boat, frees Mechadi and the crew, and prevents the hijackers from taking the Navigator although they are able to escape. The ship's captain regains control of his vessel and narrowly avoids a collision with the oil rig. Austin and Zavala borrow a helicopter from the oil rig to pursue the hijackers and locate the ore carrier Sea King that has been modified by mercenary company PeaceCo to launch helicopters.

At the American Philosophical Society in Philadelphia, assistant librarian Angela Worth helps writer Norman Stocker research a book on artichokes. Stocker finds Jefferson's message to Lewis, misfiled due to its appearance as a simple message about artichokes. Stocker shows the material to Worth, who identifies it as an encoded message from Jefferson. Worth brings the Jefferson file to her boss Helen Woolsey, who claims she will investigate it. However, Woolsey is paid by Baltazar to suppress any material found on the subject. She reports the findings to Baltazar while Worth investigates on her own. Worth, an amateur cryptographer, meets with a friend at the National Cryptologic Museum. With the aid of Professor Pieter DeVries at the National Security Agency, they break the cipher. DeVries brings the decrypted message to the Bureau of Near Eastern Affairs of the U.S. State Department. Devries and State Department staffer Hank Douglas agree that the discovery may destabilize the Middle East, especially if it leads to Israel deciding to build a Third Temple on the Temple Mount in Jerusalem, a site contested by Muslims and Jews.

At the Iraqi embassy to the U.S., Mechadi attends an event to promote the museum tour which is to use the Navigator as its central feature. Also present are Baltazar and Anthony Saxon, an adventurer and amateur archaeologist who has written books arguing Phoenicians actively traveled to North America who tells Mechadi he has long been interested in the Navigator. Mechadi invites Baltazar and Austin to see the Navigator at a Smithsonian warehouse in Maryland. Although uninvited, Saxon also arrives and extensively photographs the statue. Mechadi accepts Baltazar's offer to arrange secure transportation for the statue in the future. However, the men who arrive to transport the statue are actually Baltazar's mercenaries. They steal the Navigator after Adriano incapacitates Mechadi. Austin is contacted by State Department staffer Elwood Nickerson, who asks him to investigate the Jefferson file, hoping that if Austin discovers something less significant than the Ten Commandments they can avert any unrest in the Middle East.

Austin and Mechadi visit Jon Benson, a National Geographic photographer who documented the 1972 excavation of the Navigator in Syria. They find Adriano has already arrived, assaulted Benson and stolen his negatives of the dig. Austin notices Benson has a small figurine of the Navigator which he purchased in Istanbul. Hoping that the figurine was modeled from another version of the Navigator that may reveal why someone is so interested in the statue, Austin and Mechadi decide to locate it. Austin and Mechadi travel to Istanbul and meet in the Basilica Cistern with antiquity smuggler Cemil who directs them to a shop in the Grand Bazaar selling the figurines. The storekeeper buys the figurines from a sculptor in Kayaköy, an abandoned village turned tourist attraction. They meet with the sculptor who tells them he bases the figurines on a statue found in a Lycian tomb on the Turquoise Coast but that since he discovered the tomb it has fallen into the sea due to an earthquake. Austin and Mechadi elude a pair of Turkish pursuers and travel to Fethiye. They hire a boat and are joined by Zavala, who had been in Istanbul helping to excavate ancient harbor facilities and brings a wet submersible resembling a Corvette. Using the Subvette, they locate the relatively undamaged second Navigator. However, while Austin and Zavala are submerged Balthazar's men seize their boat. Austin and Zavala fight them off. They then make a plaster mold of the statue and dump it back into the water. Back in Istanbul, Dr. Hanley, the director of the harbor excavation, helps them create a full plaster of Paris reproduction.

They find that the statue contains a concealed map revealing the location of a Phoenician wreck in the Chesapeake Bay. They locate the ship and find the remains of another wreck diver who was wearing World War II-vintage diving gear. Using the serial number on his dive helmet, they are able to locate his widow who reveals that he recovered some gold and an amphora from the wreck. However, Saxon purchased the amphora earlier that day, having located the widow first using his photos from the Maryland warehouse. Saxon and Austin work together to salvage a parchment inside the amphora which reveals the relic was placed in a Phoenician gold mine in St. Anthony's Wilderness, an undeveloped area of modern Pennsylvania which Saxon had previously investigated as a possible location of Solomon's mines. Saxon suggests a specific cave that yielded some gold in the 19th century. Zavala and fellow NUMA employees Paul and Gamay Trout dive in the now-flooded cave and find the relic had previously been removed by Jefferson, who used the site to conceal the complete map of Solomon's mines instead.

Mechadi meets with staff at the Metropolitan Museum of Art to plan the Navigator exhibition, but Adriano kidnaps her after the meeting and brings her to Baltazar's estate in upstate New York where he reveals that he believes both he and Mechadi are descendants of King Solomon and proposes they have children to continue their line but Mechadi rejects him. He lures Austin to his estate by saying he will exchange him for Mechadi. Austin arrives and Baltazar makes him joust with him to win Mechadi's freedom. Although Austin wins the joust, Baltazar deceives and tries to kill him. Austin escapes and Baltazar flees to his ancestral home, a castle in Cyprus where he plans to sacrifice Mechadi to Baal, a Phoenician deity still worshiped by his family. Austin beats Baltazar to Cyprus with the aid of a friend in the CIA who allows him to use an SR-71 Blackbird. He and a few CIA agents overpower Baltazar's mercenaries, rescue Mechadi, and kill Baltazar. Subsequently, Austin lures Adriano to Solomon's cave and traps him underwater to die.

Austin and Mechadi learn that Jefferson concealed the relic at Monticello where it is watched over by a secret society, the Artichoke Society, who will decide when and if it can safely be revealed to the world. Saxon plans on continuing his long-running search for the tomb of the Queen of Sheba and Mechadi agrees to assist him.

Kirkus Reviews described The Navigator as "A small—very small—step up from Saturday morning adventure cartoons."^[2] Publishers Weekly described it as one of the weaker titles in the NUMA Files, criticizing it for predictable action and describing the writing as "often less than Cussler's best."^[3]