TAWI-TAWI ISLAND, Philippines -- As the 10 men approached, the crowd parted in front of them. When they were about 20 feet away, I noticed that they were all wearing the uniform of the Moro National Liberation Front -- not long ago considered a vicious terrorist organization. The U.S. Navy SEAL standing beside me edged closer, his short-barrel carbine at the ready.

"We want to tell you why we are here," said the apparent leader of the small band of men. He spoke in Tausig, one of several dialects spoken on this tiny island, and he waited patiently for our interpreter to translate into English. His comrades looked about, seemingly bemused at the hubbub they had created.

Tawi-Tawi is one of the most remote of the 7,100 islands in the Philippine archipelago. Just 25 nautical miles from Malaysia, and less than 5 degrees north of the equator, its name means "Far-Far" in Malay. To get here our FOX News "War Stories" team flew to a Philippine Navy base aboard a U.S. Navy H-60 helicopter, and then boarded two patrol boats with Philippine SEALs and their U.S. counterparts. After a swift transit through crystal blue water, we arrived at the coastal village of Balingbing, where many of the 12,000 mostly Muslim inhabitants live in homes built on wooden stilts over the sea.

The ostensible purpose of our visit was to document the opening of a new boat dock, set to coincide with the 109th anniversary of Philippine independence. On June 12, 1898, Emilio Aguinaldo had marched triumphantly into Manila and declared victory over Spain -- but that wasn't the only reason several thousand people were clamoring over the shore of this seaside town. What had brought them -- and the uniformed men from the MNLF -- to the waterfront was a ribbon-cutting ceremony for a new boat landing.

Designed and built for less than $75,000 by the U.S. Agency for International Development (USAID) with a 25 percent contribution from the provincial government, the opening of the new pre-cast concrete commercial pier was wildly applauded by the island's inhabitants. Nearly all of them reap their livelihoods from the sea -- as fishermen, shrimpers or seaweed farmers. Noel Ruiz, the engineer who supervised the construction for USAID, noted, "Most Americans would see this as a very modest project, but for the people of Tawi-Tawi this boat landing is proof that the Philippine and American governments really do care about what's happening here."

And what's been happening here isn't just good news for the predominantly Muslim population on a tiny island in the Sulu Sea, it's also good news for America's war against Islamic terror.

"For years these islands were havens for radical Islamic groups like Abu Sayyaf and Jemaah Islamiyah," said Lt. Col. Arturo Biyo, commanding officer of the Philippine 2nd Marine Battalion Landing Team, headquartered on Tawi-Tawi. "If things had not turned around down here," he added, "these islands could well have become a new training ground for international terrorists -- just like Afghanistan in the 1990s."

Col. Biyo should know. In January, his battalion succeeded in tracking down Judnam Jamalul, a notorious Abu Sayyaf commander who had dubbed himself "The Black Killer." Maj. Joseph Cuizon, the Marine Battalion Executive Officer, personally led the 14-man force that found and killed "the killer." When I asked him what turned things around, his reply was straightforward: "Good intelligence, the appropriate use of force when necessary and consistent civil-military programs that help the people. And here, the third is essential for the first two."

These sentiments are echoed by others with experience in this region. Armando de Rossi is an Italian immigrant to the United States and a highly successful engineer who has worked on hydroelectric projects all over Asia for more than 30 years. He says, "The Muslims in the Southern Philippines don't hate Americans and they don't like the terrorists. But they need education. They need jobs to put food on the table for their families. They need decent medical care when they are sick or hurt." De Rossi doesn't just talk the talk -- he walks the walk. His 3P Foundation, a privately funded charity devoted to the "promotion of peace and prosperity," is complementing the work done by USAID by building water supply systems, donating ambulances, training first-responders and building schools.

Do those kinds of things really change hearts and minds? The lean men in the MNLF uniforms had the answer to my question. "We used to fight against our government, but we are here today to thank America for Arms to Farms," a U.S.-Filipino program initiated when a peace deal was struck with the MNLF. "I am now a seaweed farmer," their leader said through our interpreter. Then in broken English he added proudly, "and today I have a daughter in college."

It's an interesting photo: a gray-haired retired U.S. Marine they took to calling "The Silver Fox" towering over smiling men once wanted for acts of terrorism. It's enough to make one wonder if this way of combating radical Islam might work elsewhere.