The military action came hours after talks in Tokyo between Indonesian officials and leaders of the Free Aceh Movement broke down late Sunday. The meeting reportedly collapsed after rebels rejected a government proposal for limited autonomy within Indonesia.
Indonesian President Megawati Sukarnoputri declared martial law in the region, signing an order that gave the military the power to make arrests, limit travel, and impose curfews on the province's 4.3 million people, the Associated Press reported.
"All the parts of Aceh province are declared as being in a dangerous situation with their status now under a military emergency," the decree, which was read out at midnight by a presidential aide, said.
Senior military officers in the Indonesian capital, Jakarta, told reporters that they wanted to emulate U.S. success in Iraq with an overwhelming show of force, according to National Public Radio. The military has even "embedded" local reporters with units.
Nearly 500 Indonesian soldiers parachuted from six C-130 Hercules transport planes into an airfield in the western end of the province near Banda Aceh, the province's capital, located on the northwest tip of the island of Sumatra. Indonesian planes also fired rockets at a suspected rebel base some 12 miles east of the capital, according to Agence France-Presse.
"I have ordered soldiers to hunt for these [rebels] who refuse to surrender ... hunt for them and destroy them to their roots," Indonesian military chief Gen. Endriartono Sutarto told the AP.
Some 600 other soldiers landed from one of 15 warships patrolling the coast of a region with a heavy concentration of rebel forces, Maj. Gen. Erwin Sujono told reporters.
Military officials told reporters the operation, which could include attacks from the air and the sea, may last up to six months.
Meanwhile, Indonesian authorities have reportedly already arrested five senior rebel leaders, named as suspects in a series of recent bomb attacks, Col. Surya Darma, Aceh's chief police detective, told the AP.
One of the more conservative Islamic provinces in the world's most populous Muslim nation, Aceh has been the scene of fighting between the government and independence-seeking rebel groups since 1976.
Aceh was a part of the new Indonesia when the country gained independence from the Dutch in 1945, but soon began efforts to break away from the sprawling archipelago.
After years of struggle beginning in the early 1950s, Jakarta granted Aceh "special region" status in 1959, allowing the region an "unusually high degree of autonomy in religious, educational and cultural matters," The Jakarta Post reported, including higher than usual respect for local Islamic customs.
Tensions flared again with the Free Aceh Movement's founding in 1976. The group went underground in the late 1970s after a government crackdown, but resurfaced in the 1980s and has since led an increasingly militant offensive against Indonesian rule. During the 1990s, small rebellions sporadically erupted in the region, but were quickly put down by Indonesian authorities.
After East Timor voted to secede from Indonesia in 1999, emboldened Aceh resistance leaders fought for a similar independence referendum. However, Megawati has consistently opposed full independence for the region.
In an attempt to stem the violence and defuse rebel anger, the government allowed Aceh to enact Muslim sharia law last year -- the only province in the archipelago to officially abide by the strict Muslim dictates. Nonetheless, rebels say they are fighting for an independent state, not an Islamic one.
Aceh is rich in deposits of oil and natural gas, but rebel leaders have long argued that Indonesia siphons away much of the money earned from the region's resources. Indonesian officials have maintained that Aceh's exports are vital to the country's economy.
The fighting in Aceh has killed an estimated 12,000 people since 1976. A cease-fire signed December 9 called for an end to violence in the region, troop reductions and international observers to monitor the armistice. However, the agreement did not promise an independence referendum or specify how to demilitarize the province, and the violence has continued. During the conflict, both sides have been accused of human rights abuses.
Indonesian military spokesman Maj. Gen. Syafrie Syamsuddin told AFP that rebel forces in Aceh numbered some 5,000. He said around 28,000 Indonesian troops were already stationed in the province, and the operation launched Monday will add more than 1,000.