According to James Robert Parish, in his book Fiasco: A History of Hollywood's Iconic Flops, the idea for the Popeye musical had its basis in the bidding war for the film adaptation of the Broadway musical Annie between the two major studios vying for the rights, Columbia and Paramount. When Robert Evans found out that Paramount had lost the bidding for Annie, he held an executive meeting in which he asked about comic strip characters that they had the rights to which could also be used in order to create a movie musical, and one attendee said "Popeye".
At that time, even though King Features Syndicate (now a unit of Hearst) retained the television rights to Popeye and related characters, with Hanna-Barbera then producing the series The All-New Popeye Hour under license from King Features, Paramount still held all theatrical rights to the Popeye character, due to the studio releasing cartoons produced by Fleischer Studios and Famous Studios, respectively, that lasted from 1932 to 1957.
Evans commissioned Jules Feiffer to write a script. In 1977, he said he wanted Dustin Hoffman to play Popeye opposite Lily Tomlin as Olive Oyl, with John Schlesinger directing.
In December 1979, Disney joined the film as part of a two-picture co-production deal with Paramount which also included Dragonslayer. Disney acquired the foreign rights through its Buena Vista unit; the deal was motivated by the drawing power that the studio's films had in Europe.
The film was shot in Malta. The Sweethaven set that was built for the film still exists, and it is now a popular tourist attraction known as Popeye Village. According to Parish, Robin Williams referred to this set as "Stalag Altman".