Following World War II, an entire destroyer escort, the U.S.S. Kornblatt, has mysteriously gone missing. Lieutenant John Paul Steckler VII, the last of a long line of good-natured but screw-up U.S. Navy officers, was tasked with commanding the Kornblatt to its decommission back in the U.S., but somehow the ship disappeared without a trace on its homeward voyage. Now, with a $4 billion appropriation at stake, Congressman Mandeville refuses to approve the funds until the Kornblatt is found. Steckler's former superior, Vice Admiral Bludde, who has been trying to sugarcoat this embarrassing incident, has no other choice but to comply.
Just as he is ready to embark on a honeymoon with his freshly wedded wife Prudence, Steckler is tracked down by Navy personnel and brought to the Pentagon, where he is charged with treason and malevolent misappropriation of government property. Though he can convince the admirals of his basic innocence, he is nevertheless charged with finding the Kornblatt within the next ten days, thus upsetting both his wife and his honeymoon plans. Since he is at a loss to explain the whereabouts of the ship, Steckler is teamed up with Naval Intelligence operative Ensign Benson, who happens to be an attractive woman.
Benson employs a relaxing therapy to coax Steckler's memory, succeeding with much effort. In a flashback, it is told that on the day hostilities in the Pacific were finally ended, the Kornblatt was ordered to return to Pearl Harbor for the decommissioning of those crew members with sufficient discharge points. Steckler, assisted by Ensign Stan Wychinsky and the remaining crew, attempted to get the Kornblatt back to the mainland, but Steckler got the ship stuck on a reef near an island occupied by a garrison of still-entrenched Japanese soldiers. Captured by those soldiers while exploring, Steckler was imprisoned for a night before his impending execution, only for the Japanese commander, Colonel Takahashi, to learn that the war really was over. By the time of Steckler's release and the garrison's surrender to him, however, the Kornblatt and her crew, believing him dead, had already departed.
With Wychinsky being the only viable lead, Steckler and Benson track him down in Miami, Florida, where he works as a professional wrestler. From him, they learn that he has turned the Kornblatt over as instructed, but being in the middle of a match, he loses the memory of the responsible official's name when his opponent whacks him on the head. Grounded by a hurricane, and unwilling to spend any more time separated from Prudence, Steckler takes a train back to Washington, where he is forced to share a compartment with Benson (who incidentally takes a personal liking to him); this circumstance leads to a prompt misunderstanding with Prudence at the Washington railway station, who leaves him in a fury. In addition, Mandeville has drastically cut the time limit in favor of an immediate inquiry on this very day.
In the meantime, Wychinsky, who has finally remembered what happened to the Kornblatt, has followed Steckler back to Washington and encounters Prudence. The two proceed to the hearing, which is (due to Mandeville's animosity) progressing very badly for Steckler and Bludde. Given a reprieve of 48 hours, Steckler and Wychinsky go to a spot in the ocean where the wreck of the Kornblatt lies following her last use as a target dummy. After a harrowing dive and struggle with nitrogen narcosis and a hungry kraken, they recover a bell from the Kornblatt, thus confirming the ship's fate, and back at the inquiry Mandeville is revealed as the man who had unwittingly assigned the Kornblatt for target practice, ignoring the red tape. Finally, rehabilitated, Steckler manages to secure a significantly higher appropriation for the Navy, and is happily reunited with Prudence.
