Chris O'Donnell was first offered the role of J. David Schwimmer was asked to play the role of J before Will Smith, but turned it down.

Clint Eastwood was offered the role of K but turned it down.

Bruce Campbell was set to appear in a small role, but he backed out to star in the television film Tornado! (1996) (TV).

Quentin Tarantino was originally offered the chance to direct, but turned it down.

The "known aliens" visible on the screen include Al Roker, Isaac Mizrahi, Danny DeVito, director Barry Sonnenfeld, Chloe Sonnenfeld (Barry's daughter), Sylvester Stallone, Dionne Warwick, Newt Gingrich, Anthony Robbins, George Lucas, and executive producer Steven Spielberg.

Director Barry Sonnenfeld replaced Les Mayfield shortly before production began.

During the shoot, there was a script revision which changed the role of the 'Universe' in the movie. Fortunately, some creative tricks could be used to avoid having to re-shoot several scenes. For instance, the dialogue between Rosenberg and the tall man in the diner was originally in English (and they were adversaries), but their lines were simply dubbed in an alien language that could be subtitled with the desired explanation. New lines were also written for Frank, the talking dog, whose scenes had to go through post-production anyway. Director Barry Sonnenfeld could be heard on the DVD bonus material jokingly advising fellow directors to include a talking dog into every movie, which makes it easy to change the plot while filming.

John Turturro was offered the role of Edgar, but had to decline due to other commitments.

After Linda Fiorentino "won" her role in Men in Black in a poker game with director Barry Sonnenfeld, he warned her that she would not be in any nude scenes.

In the scene where K takes J through the arrivals and customs area, there is an alien father and son. The actress who played the father is Debbie Lee Carrington, who went on to play Mini Mimi on "The Drew Carey Show" (1995), while the son was played by Verne Troyer, who went on to play Mini Me in Austin Powers: The Spy Who Shagged Me (1999).

Will Smith, after reading the script, did not want to accept the role. It was his wife Jada Pinkett Smith that convinced him to take the part.

The housewife being named "Beatrice" is a reference to the Kurt Vonnegut Jr. novel "The Sirens of Titan," first published in 1959.

When K reveals there are about 1500 aliens on Earth and most of them are on Manhattan just trying to make a living, James asks "Cab drivers?". In "So long and thanks for all the fish" (part of the "Hitchhiker's Guide to the Galaxy" series), Ford Prefect submits an entry to the Guide hinting that driving a cab is a good way to make a living for aliens visiting New York.

According to the computer when his identity is being erased, Will Smith's character James D. Edwards III had the social security number 905-80-5406.

Producer Steven Spielberg hired Jurassic Park (1993) and The Lost World: Jurassic Park (1997) collaborator David Koepp to do an uncredited rewrite.

Through an apparent lab error, at least portions of the release prints used in the U.S. were not hard matted for spherical widescreen projection. This meant that if the projectionist did not properly frame the projected image, the audience would be able to see lens shades, microphones and other things not normally visible in the frame area.

The Stadium the ship flies over during the baseball games is Shea Stadium in Flushing, Queens NY. The player that gets hit on the head with the fly ball is then NY Mets outfielder Bernard Gilkey.

The examination room of the MIB headquarters was modeled on the TWA terminal at JFK International Airport (note the Arne Jacobsen Egg chairs).

The film's climax takes place on the site in Flushing Meadows, New York, where the 1964 World's Fair was held.

The MIB headquarters are located in the ventilation tower of the Brooklyn-Battery Tunnel, which connects Manhattan with Brooklyn.

To make them into credible flying saucers, the CG renditions of the towers at Flushing Meadows, Corona Park, where the finale takes place, are substantially different from the actual buildings. Primarily, there are actually three structures of varying height, not two as shown in the film. Additionally, the saucer dish of the shortest tower intersects with the poles of the taller ones, and the dish of the mid-sized tower intersects with the pole of the largest one. Therefore, there is really only one complete saucer - on top of the tallest building. Moreover, the dish atop the highest tower is double the thickness of the shorter tower, not equal as depicted in the film.

The line Will Smith says after jumping on the double-decker bus, "It just be raining black people in New York", was improvised on the set, but the producers like it so much that they kept it.

When Kay tells EdgarBug that he is in violation of section 4153 of the Tycho Treaty, this is a reference to director Barry Sonnenfeld's birthday, 1 April 1953.

Originally there were going to be two huge alien spaceships looming over Earth: an Arquillian ship and a Baltian ship, with representatives of both species staking claim of the galaxy. Mr. Rosenberg (the "little dude in the big dude's head") was a Baltian (confirmed by the novelization of the film), while the tall alien (Carel Struycken) he met at the restaurant was an Arquillian (and is so listed in the end credits). After some choice editing and rewriting, Rosenberg became an Arquillian.

During the opening credits they were originally going to use the song, "Over the Rainbow".

Yasushi Nirasawa worked on some designs for the Edgar Bug which ultimately went unused. One of his takes on the Edgar Bug was a creature more humanoid in form, with two heads and very long arms which resembled the forelegs of a praying mantis.

The photo of Will Smiths character when K (Tommy Lee Jones) is erasing the data is an old high school photo of Will.

Henrik Thor-Larsen, the designer of the Ovalia Egg Chair, received punitive damages from the film studio after they copied his chair without permission in order to have enough of them for the scene where the recruits assemble at MiB headquarters for the test.

Actor Vincent D'Onofrio researched his role as Edgar by watching a lot of bug documentaries. In order to achieve his character's distinctive walk, he put on knee braces so he couldn't bend his legs, and taped up his ankles.

Tommy Lee Jones and Rip Torn appear together in this film. Though it is their first film together, Jones has frequently worked with Torn's cousin, Sissy Spacek, having appeared with her in Coal Miner's Daughter (1980), JFK (1991), and The Good Old Boys (1995) (TV).

When Edwards (Will Smith) jumps from the overpass onto the tour bus, he jumps from the same bridge where Robert Neville is attacked by the demon dogs after the sun goes down in I Am Legend (2007).

The double-action revolver carried by the tow-truck driver and later by Edgar in the morgue scene is a Ruger Super Redhawk .44 Magnum, which is available in two barrel lengths. This one has a 9-1/2" barrel and weighs 58 ounces (i.e., a little over 3-1/2 pounds) empty.