Set approximately two years after the original film, Beverly Hills Police Captain (formerly Lieutenant) Andrew Bogomil (Ronny Cox), Detective Billy Rosewood (Judge Reinhold), and Sergeant John Taggart (John Ashton) are trying to figure out who is behind the "Alphabet Crimes," a series of mostly high end store robberies distinguished by their monogrammed envelopes with an alphabetical sequence the assailants leave behind. Complicating matters is the new "political" state of the Beverly Hills police, headed by an incompetent and verbally abusive new police chief Harold Lutz (Allen Garfield), who is doing everything he can to stay on Mayor Ted Egan's (Robert Ridgely) good side. Unimpressed when Rosewood calls the FBI to help solve the case, Lutz holds Bogomil responsible as commanding officer and suspends him, despite Bogomil's efforts to convince him that Rosewood was only following a hunch, a traditional aspect of police work. Lutz also punishes Taggart and Rosewood by placing them on traffic duty.
On the way home, Bogomil is shot by Karla Fry (Brigitte Nielsen), the chief hench-woman of Maxwell Dent (Jürgen Prochnow). Finding out about the shooting over a news report, Axel Foley (Eddie Murphy) immediately flies out to Beverly Hills (covering his absence from his actual job in Detroit by telling his commanding officer Inspector Todd he was going "deep deep deep DEEP undercover" on the credit card fraud case he had been assigned to) to help find out who shot Bogomil to repay the favor he owes Bogomil for saving his job two years ago.
After arriving in L.A., Foley shacks up in a Beverly Hills mansion which is under construction while the owners are on vacation and sets it as his base of operations. Foley then goes to the police station and makes contact with Taggart and Rosewood who secretly agree to assist Foley because of Lutz's apparent attempts to find an excuse to get them fired. Posing as an undercover FBI agent to get past Lutz (by convincing his would-be partner Jeffrey Friedman in Detroit to pose as Todd to intercept Lutz's phone call to Todd's office and convince Lutz that Foley is part of a multi-jurisdictional task force). Foley soon starts making the connection between the robberies and Dent. Foley then asks Bogomil's teenage daughter, Jan, use her connections as an insurance agent to find out about Dent's financial dealings.
It turns out that Dent is robbing his own businesses deliberately (which have insurance) to finance firearms deals and is discreetly using his henchman Charles Cain (Dean Stockwell) as the front man for his operations. Bogomil was shot because he was on the right track with his investigation into the case.
Having foiled a robbery attempt at a bank depository, Foley is able to trick Dent's accountant Sydney Bernstein into using his computer and discovers that Dent and Karla are planning to leave the country, and he also learns from Jan that all of Dent's businesses have gone under except his race track, which he is convinced is the next target.
On the way Foley solves the latest riddle sent to the police, and is convinced that this riddle was intended for the cops to solve so Dent could implicate Cain as the Alphabet Bandit (though Foley is aware that Cain is not intelligent enough to be the Alphabet Bandit, having met him personally at Dent's gun club and getting an impression that he is a pawn).
The three arrive too late to stop the robbery and find Cain's body (he was shot by Karla) among those killed. While Lutz announces publicly that the Alphabet Crimes have been solved, Foley notices some red mud at the stables, which leads him, Taggart and Rosewood to Dent's oil field where Dent is making his final arms deal. The three of them then engage in a shootout with everyone involved in the deal. Dent confronts Foley in the warehouse, but Foley gets distracted and Dent walks into the shadows. Dent then crashes through the wall in his car and Foley shoots Dent through the windshield, sending his car down a hill and erupting in flames. Karla appears and is about to kill Foley, but is shot dead by Taggart.
Just as the last thugs are about to flee, the police arrive upon the scene, along with Lutz and Mayor Egan. Lutz tries to fire Rosewood and Taggart for their insubordination as well as arrest Foley. However, both Taggart and Rosewood stand up to Lutz this time and prove that Dent was the real Alphabet Bandit. They are also able to convince Mayor Egan of Lutz's incompetence, and the Mayor personally fires Lutz because he is tired of his abusive attitude towards his own men.
At the end, Bogomil is chosen by Mayor Egan to replace Lutz as the new Chief of Police, and Foley returns to Detroit, but not before he gets chewed out by Inspector Todd over the phone, right after Egan called him to congratulate him on allowing Foley to assist them on this case. On top of that, Jeffrey Friedman is revealed to have accidentally wrecked Foley's car while covering for him. Rosewood and Taggart say their goodbye to Foley for good when the owners of the Beverly Hills mansion return from their vacation to find Foley and the two detectives there, forcing Foley to flee to the airport and leaving Rosewood and Taggart to explain to the owners what they are doing in their house.