Oliver Stones's violent satire on the media was first submitted to the BBFC in August 1994, against a backdrop of controversy over media effects that had built up in the wake of the murder of James Bulger in 1993. The version submitted to the BBFC had already been subjected to over three minutes of cuts by the MPAA (the American classification body) in order to obtain a more commecial R rating.

Nonetheless, there were still calls for what was already a much-reduced version of the film to be banned, particularly in certain sections of the press. Although the BBFC was content that the film was acceptable at 18 for cinema release, without further cuts, a final decision was delayed until the BBFC had time to investigate a number of press reports linking the film to killings in America and France.

The idea that ordinary people had been turned into killers by being exposed to a particular film was not one with which the FBI or local police forces in America had any sympathy.

In all but one of the American cases linked by the press with the title of the film, the accused or dominant member of an accused pair had been in prison and, in one case, also in a mental hospital, for serious acts of violence, including in three cases of murder. In the remaining case, an intention to commit the offence had been stated to a friend many months before the killing and access to guns established. In the two cases where a series of killings was attributed to an accused pair, the first killing had been committed before the film opened and there was no evidence that the accused had ever even seen the film. On the other hand, drugs seemed to have been involved in all the American cases. The one case in France turned out to have been politically motivated, the killers having formed their own anarchist group well in advance of the crime and having been supplied with a pump-action shotgun by two other anarchists who have been imprisoned for complicity in the offence. There was no evidence in that case that either of the accused had ever seen the film in question.

Having satisfied itself that the film Natural Born Killers has not had the pernicious effect it was reported as having, the BBFC finally awarded a cinema certificate on 19 December 1994. It opened in UK cinemas in February 1995.

The video version of the film was not submitted to the BBFC until January 1996. Once again, the BBFC considered the film carefully in terms of the tests laid out by the Video Recordings Act 1984 (as amended by the Criminal Justice Act in 1994). Although strong, the Board considered that the film was a serious and effective satire about violence and media responses to violence and did not consider that the film was likely to promote or glamorise violence. It was therefore passed '18' uncut for video release on 26 February 1996.

At this point it looked likely that Natural Born Killers would be released on video in March 1996 and gradually fade away from public attention. However, 13 March 1996 saw the murder of several schoolchildren by a gunman in Dunblane in Scotland. This horrific event reignited the whole debate about media violence and its possible effects, resulting in the tabling of a motion in the House of Commons objecting to the BBFC's classification of the video.

The film's distributor was simultaneously coming under increasing pressure not to release the video and took the unusual step of asking the BBFC to reconsider its decision. The BBFC responded that it was not within the BBFC's powers to withdraw a certificate once it had been issued and that, in any case, the BBFC did not regard the film as dangerous. Nonetheless, the BBFC did point out that the distributors were under no obligation to release the video in the UK. As a result, the release of the video was cancelled by its own distributors indefinitely.

The video version therefore remained unavailable in the UK until 2001, when the distributors reconsidered and gave the film a belated release on video and DVD. Bizarrely, the film had been shown in the interim on Channel 5 television, despite its continuing unavailability on video.

In 2002 the full 'Director's Cut' version of the film, restoring the three minutes of cuts required in the US in 1994, was submitted to the BBFC and classified 18 uncut.