London police said two men aged 48 and one aged 56 were arrested on suspicion of corruption early in the morning at homes in and around London. A 42-year-old man was detained later at a London police station.
Murdoch's News Corp. confirmed that all four were current or former Sun employees. The BBC and other British media identified them as former managing editor Graham Dudman, former deputy editor Fergus Shanahan, current head of news Chris Pharo and crime editor Mike Sullivan.
A fifth man, a 29-year-old police officer, was arrested at the London station where he works.
Officers searched the men's homes and the east London headquarters of the media mogul's British newspapers for evidence.
The investigation into whether reporters illegally paid police for information is running parallel to a police inquiry into phone hacking by Murdoch's now-defunct News of the World.
Police said Saturday's arrests were made based on information provided by the Management and Standards Committee of Murdoch's News Corp., the internal body tasked with rooting out wrongdoing.
News Corp. said it was cooperating with police.
"News Corporation made a commitment last summer that unacceptable news gathering practices by individuals in the past would not be repeated," it said in a statement.
In an email to staff after the arrests, Tom Mockridge - chief executive of Murdoch's British operation, News International - said the internal investigation into wrongdoing at The Sun "is well advanced."
"News International is confronting past mistakes and is making fundamental changes about how we operate which are essential for our business," Mockridge said.
"Despite this very difficult news, we are determined that News International will emerge a stronger and more trusted organization," he added.
Thirteen people have now been arrested in the bribery probe, though none has yet been charged. They include Rebekah Brooks, former chief executive of Murdoch's News International; ex-News of the World editor Andy Coulson - who is also Prime Minister David Cameron's former communications chief; and journalists from the News of the World and The Sun.
Two of the London police force's top officers resigned in the wake of the revelation last July that the News of the World had eavesdropped on the cell phone voicemail messages of celebrities, athletes, politicians and even an abducted teenager in its quest for stories.
Murdoch shut down the 168-year-old tabloid amid a wave of public revulsion, and the scandal has triggered a continuing public inquiry into media ethics and the relationship between the press, police and politicians.
An earlier police investigation failed to find evidence that hacking went beyond one reporter and a private investigator, who were both jailed in 2007 for eavesdropping on the phones of royal staff.
But News Corp. has now acknowledged it was much more widespread.
Last week the company agreed to pay damages to 37 hacking victims, including actor Jude Law, soccer star Ashley Cole and British politician John Prescott.
The furor that consumed the News of the World continues to rattle other parts of Murdoch's media empire.
As well as investigating phone hacking and allegations that journalists paid police for information, detectives are looking into claims of computer hacking by Murdoch papers.
News Corp. has admitted that the News of the World hacked the emails as well as the phone of Chris Shipman, the son of serial killer Harold Shipman. And The Times of London has acknowledged that a former reporter tried to intercept emails to unmask an anonymous blogger.
News Corp. is preparing to launch a new Sunday newspaper - likely called the Sunday Sun - to replace the News of the World.