The bill was approved at a Cabinet session late Wednesday, Justice Minister Kunio Hatoyama told reporters. The measure must now be approved by the country's parliament.
The new bill would limit Japanese ships to refueling and supplying water to ships on anti-terrorism patrols, but does not allow them to refuel vessels involved in military operations, such as attacks, as well as other activities including rescue operations and humanitarian relief.
Prime Minister Yasuo Fukuda's government made the changes in the mission, which started in 2001, in hopes of mollifying opposition critics who said it involved Japan too deeply in military operations in Iraq and Afghanistan.
The opposition Democratic Party of Japan, or DPJ, controls the upper house of parliament, giving it the power to slow - but not definitively kill - the ruling bloc's legislative agenda. Top ally the United States, meanwhile, has clamored for extension of the mission.
The current mission expires Nov. 1. The new bill was to go to the Diet, or parliament, for a plenary vote.
The government has argued strenuously for the extension, saying that pulling out would leave Japan - which depends on the Middle East for almost all of its oil imports - sidelined in the fight against global terrorism.
"It's clear to anyone that this bill is the biggest issue facing parliament. The Cabinet is set to approve the bill tonight, and is determined to secure parliamentary approval," Chief Cabinet Secretary Nobutaka Machimura told reporters. "I am confident of winning support from the opposition."
Currently, 17 vessels from eight countries - the U.S., Britain, France, Germany, Pakistan, Canada, New Zealand and Japan - are participating in the Maritime Intercept Operations, or MIO, in the Indian Ocean and the Persian Gulf as part of the U.S.-led Operation Enduring Freedom, which also involves 20 countries deploying ground troops to Afghanistan.
The new bill limits Japan to refueling and water supplying of the vessels used in the OEF's maritime operation, which involves monitoring and inspection of suspected terrorist vessels, while serving as a deterrence to the proliferation of terrorism and arms smuggling.
Hoping to secure a settlement before the mission's expiration, Fukuda showed willingness to negotiate a compromise with the opposition. Still, Japan's temporary withdrawal from the mission seems inevitable.
Opponents have criticized the mission as a "free gas station," but officials say the operation allows the country to participate in the fight against terrorism while not violating its pacifist constitution.
"Though the mission is scaled down, Japan is better off keeping its presence there," said Tsuneo Watanabe, adjunct fellow at the Center for Strategic and International Studies in Washington, D.C.
In Washington, Lt. Gen. Carter Ham, the chief of operations for the Joint Chiefs of Staff, said Japan's refueling "has been deeply appreciated and very meaningful," and that the vessels serving OEF "would very much like for that to continue."
The DPJ demands the mission be scrapped, saying coalition military operations in Afghanistan there were not properly approved by the United Nations. They say the mission violates Japan's war-renouncing constitution and have alleged the oil supplied by Japanese ships was diverted to the U.S. war on Iraq.
The DPJ was to submit its own bill focusing on humanitarian support for Afghanistan.
Public opinion has been divided.
The latest newspaper poll by the Asahi newspaper on Tuesday showed 39 percent of 2,113 respondents supporting Japan's naval mission, with 44 percent opposing. No margin of error was provided.
Japan provided ground troops for a humanitarian mission in southern Iraq in 2004-2006 to back the U.S. invasion of Iraq. Tokyo has since expanded its Kuwait-based airlifting support.