Oswald is a sailor who works on the ship of the admiral. One day when work was dismissed, he looks forward to find a date at a lighthouse.
Minutes afterward, Oswald arrived at the lighthouse. To get the attention of his special someone, Oswald sings while a couple of sparrows played an accordion. Looking out the window of the lighthouse was a girl cat who was entertained by Oswald's performance. To get inside, Oswald springs himself upward using the accordion. Oswald then notices that the girl cat was having an affair with the admiral who orders him to return to the ship.
Back in the vessel, Oswald was assigned to scrub the ship's main floor and polish the cannons. To make his jobs more interesting, he comes up with an eccentric method by riding behind two runaway tabbies and at the same time scrub the floor with brushes attached to his feet as he gets pulled. This strategy turned out to be very difficult to control as it resulted in Oswald accidentally stripping paint off of some life boats as well as knocking down the admiral.
The admiral was most dissatisfied and literally kicks Oswald out of the ship. The kick was so powerful that Oswald was sent airborne for a few miles. The rabbit ends up landing in knickers that are hanged on a clothesline. At the end of the clothesline lies the window of the lighthouse which was right next to Oswald. Once more the girl cat shows up and was happy to see Oswald again. The two traded kisses.
The Navy marks the beginning of Oswald's eventual evolution in the series. In the preceeding cartoons, Oswald never wore anything other than shorts. Here, he is seen in shoes. A pair of gloves and a shirt would add to his outfit the following year.