L'US Navy souhaitait utiliser une chanson lors d'une campagne de recrutement télé et radiodiffusée. Considérant le succès du groupe Village People, elle contacte le manageur Henri Belolo qui donne son feu vert pour le projet sans rétribution particulière, demandant uniquement que la Navy l'aide à tourner le clip. Moins d'un mois après, Village People arrive à la base navale de San Diego. La Navy met à leur disposition la frégate USSReasoner, quelques avions, et l'équipage du bateau (avec toutefois l'interdiction expresse de les faire danser). L'enregistrement se déroule en 1978.
Toutefois, à la suite d'une vague de protestation contre l'usage des fonds publics pour mettre au point une vidéo commerciale d'un groupe controversé[1], la Navy renonce à sa campagne promotionnelle.
Le groupe espagnol Parchís reprend la chanson en 1979, devenant l'une de leurs plus célèbres interprétations. En la armada, chantée en espagnol, est par la suite reprise par de nombreux groupes espagnols.
En 1979 également, le groupe French Navy sort une version française de la chanson: Dans la Marine[2].
Captain Jack réenregistre la chanson, qui est cette fois-ci parodiée par Billy Connolly avec "In the Brownies".
Pendant un sketch du Muppet Show, des cochons vikings dévastent un village en chantant In the Navy.
Le duo japonais Pink Lady entre dans le top 10 japonais en 1979 avec une reprise intitulée Pink Typhoon (voir l'article japonais). Dans leur interprétation, les deux chanteuses substituent les mots "Pink lady" ("Pin-ku re-di") à "In the navy" dans le refrain, et "I want you, you want Mie/I want you, you want Kei" (en référence au nom des chanteuses Mie Nemoto et Kei Masuda) à "They want you as a new recruit" dans les couplets.
Dans la comédie de David S. WardTouche pas à mon périscope, sortie en 1996, la chanson est interprétée lors du final par l'équipe du film ainsi que les Village People eux-mêmes.
Le groupe israélien Tislam, dans Tnu Li Rockn'Roll (Donne-moi du rock 'n' roll), se trouve la phrase "Hoshavt oti Ba'cheder etmol ad meuchar, lishmo'a Indeonezi shel Anshei Hakfar" (Tu m'as installé hier dans ta chambre pour écouter "Indonezi" des Village People). Cette phrase de l'auteur Yair Nitzani, provient du fait que lorsqu'il travaillait comme DJ, les gens lui demandaient fréquemment de passer la chanson "Indonezi" (signifiant "Indonésien") parce qu'ils comprenaient mal son véritable titre. Il s'agit là d'un exemple de mondegreen, l'acquisition d'une nouvelle signification pour un terme initialement mal entendu.