As reports of riots in Indonesia flashed across the world’s news wires, in May 1998, my wife telephoned the hotel in Jakarta where I was staying to make sure I was OK. “What do you see out your window?” she asked. Flames from burning department stores and Chinese shops and businesses owned by the family of President Suharto spread across the horizon like a magnificent sunset. Army tanks and soldiers with dogs filled the square below. “I see a city burning,” I said, “a city dying.”

At the time it seemed no exaggeration. Indonesia’s economy and its currency, the rupiah, had collapsed in a financial crisis that gripped all of Southeast Asia. In parts of the Spice Islands, which belong to Indonesia, tensions between Muslims and Christians were escalating. In the nation’s province of Aceh, and in Papua, site of one of the world’s richest deposits of copper and gold, the death toll mounted as secessionists skirmished with the army. East Timor was about to fall into anarchy, then secede from Indonesia as an independent country. In Jakarta, the nation’s capital, student protesters seeking to replace three decades of dictatorship with democracy were brutally put down by the military and government thugs, sparking clashes that would claim 1,200 lives and 6,000 buildings. Hardest hit was the Chinese minority, long resented for their entrepreneurial success; their businesses were looted and destroyed, and women were raped by hired military goons. Tens of thousands of Chinese fled the country.

I was then a reporter for The Los Angeles Times, based in Hanoi, and I was covering the civil unrest in Jakarta. One day I came upon an anti-Suharto demonstration at Trisakti, a private university. Students at other colleges sometimes taunted Trisakti’s students, belittling their lack of political involvement by waving bras and panties at them. But on this day Trisakti’s young men challenged the soldiers, standing shoulder to shoulder and pushing against their lines. “Don’t get so close. You could get shot and killed,” a friend of 19-year-old Trisakti student Elang Lesmana warned him. “That’s OK,” Lesmana replied. “I’d be a hero.” The soldiers, who had exchanged their rubber bullets for real ones, killed Lesmana and three other students. The deaths galvanized Indonesia, turning the tide of public and military sentiment.

Suharto’s top general, Wiranto—like Suharto and many Indonesians, he has only one name—told the president the military could no longer protect him and had no intention of staging a Tiananmen Square-style massacre in Jakarta. Nine days after the shootings of students, on May 21, Asia’s longest-serving leader resigned. He retired to the family compound in a leafy Jakarta suburb to live out his final decade watching TV, surrounded by a stuffed tiger and bookshelves full of cheap souvenirs and trinkets. Caged songbirds sang on his terrace.

For 32 years Suharto had run Indonesia like the CEO of a family corporation. The Suhartos’ fortune reportedly topped $15 billion, and they had a major stake in more than 1,200 companies. But Suharto left behind more than a legacy of corruption and a military best known for its deadly abuse of human rights. He had also been Indonesia’s father of development, building schools and roads, opening the economy to foreign investment, transforming dusty, tropical Jakarta into a modern capital and lifting millions of Indonesians out of poverty.

The world’s most populous Muslim country, with 240 million people, Indonesia has always been an ungainly place. The archipelago encompasses 17,500 islands—6,000 inhabited—that stretch 3,200 miles across the Pacific Ocean’s so-called Ring of Fire where earthquakes and volcanoes are a constant threat and tsunamis are born. The people—88 percent Muslim—speak scores of local languages and represent dozens of ethnic groups. As recently as the 1950s the population included tribes of headhunters. That this polyglot was born as a single nation in 1949, after 300 years of Dutch rule and four of warfare and negotiations with the Netherlands, was a miracle in itself.

After witnessing the Suharto-era meltdown, I did not return to Indonesia until October 2009, after I had begun hearing about changes unimaginable a decade earlier. On the surface, Jakarta didn’t seem much changed. Traffic remained gridlocked in the humid 90-degree heat. Shantytown slums languished in the shadow of marbled shopping malls where pianists in tuxedos played Chopin next to Valentino and Louis Vuitton shops, and white-gloved valets parked cars. The Indonesians I encountered were, as always, gracious and friendly, and I could walk virtually any street, even at night in a city of nine million people, with no fear for my safety. On one block you’d still find a mosque packed with men who considered alcohol and dancing ungodly, on the next, a nightclub like the Stadium that served alcohol 24 hours a day on weekends and boasted a disco pulsating with lights, thunderous rock music and writhing young bodies.

But beneath the surface, everything was different. Indonesia had recovered from half a century of dictatorship—first under Sukarno, then Suharto—and in the time I’d been away had become what Freedom House, a U.S. think tank, called the only fully free and democratic country in Southeast Asia. The outlying islands were generally calm. Soldiers no longer careered with abandon through city streets in cars bearing the red license plates of the military command. The unthinkable had happened: Indonesia had become one of the region’s most stable and prosperous nations.

People seldom talked about the dark past, not even of the apocalyptic end of the Sukarno regime in the mid-1960s, when the army and vigilantes went on a madhouse slaughter to purge the country of leftists, real and imagined. The killings spread from Jakarta to the Hindu-dominated island of Bali, and by the time order was restored as many as half a million had lost their lives. The mayhem was captured in the 1982 movie starring Mel Gibson and Linda Hunt, The Year of Living Dangerously.

Today Indonesia has joined the Group of 20, the world’s premier forum for economic cooperation. Blessed with an abundance of natural resources—petroleum, natural gas, timber, rubber and various minerals—and a strategic position straddling one of the world’s most important shipping lanes, it is one of Asia’s fastest-growing economies.

“There was great euphoria when Suharto stepped down, but it opened a Pandora’s box,” said Julia Suryakusuma, a Jakarta newspaper columnist. “Yes, we’ve got a real democracy. The world’s third largest after India and the United States. That’s pretty amazing. But what people worry about now is Islamization, the hard-liners who want an Islamic state.”

A soft rain was falling the night Fanny Hananto came to pick me up at my hotel. I jumped on the back of his motorcycle, and we slipped through lines of idling, bumper-to-bumper cars, headed for the mosque he attends. We passed a large group of women with small children, collectively called traffic jockeys, on a sidewalk. Hananto said solo motorists would pay a mother and child 25,000 rupiah (about $2.50 U.S.) to be passengers so the driver could use the lane reserved for cars occupied by three or more people.

I had met the 37-year-old Hananto through a friend. With his scraggly beard and a wife who dressed in black, everything covered but her eyes, and a daughter named for one of the Prophet Muhammad’s wives, Hananto seemed the very personification of Islamic purity. Had he always been religious?

“Not exactly,” he said. As a younger man, he had worked on a cruise ship, spent nights partying with drugs and alcohol and, referring to the crowd that hung out at the Stadium nightclub, said, “I was one of them.” But about a dozen years ago he grew to fear the wrath of Allah and did a 180-degree turn, embracing Islam through the Kebon Jeruk Mosque, to which he was now taking me. He so deeply trusted the imam who mentored him that when the cleric said he had found a good woman for Hananto, and showed him her picture, Hananto said, “OK, I will marry her.” He did so a short time later, never mentioning his past life to her.

I removed my shoes as we entered the mosque, fearing I might lose them amid the piles of footwear strewn about. Thursday evening prayers had attracted so many men, perhaps 2,000, that I could not even see the visiting Pakistani cleric preaching at the front. The men were members of an apolitical Islamic movement, Tablighi Jamaat, that strives to make Muslims better practitioners of their faith. I squatted on the floor, and men in long, loose-fitting white shirts and turbans nodded in welcome or reached out to shake my hand. Hananto introduced me to his friend, Aminudia Noon, a university professor of civil engineering. I asked him where the women were.

“They’re home praying,” he said. “If they were to come here, it would be like an arrow to the heart from Satan.”

Islam was brought to Indonesia not by conquest but by 12th-century Muslim traders who took cloves, nutmeg and other spices to the West. Its spread was gradual and peaceful. Rather than smothering local culture and religions—Hinduism, Buddhism, mysticism—it absorbed them. The Islam that took root was less doctrinaire and less intolerant than some forms practiced in the Middle East, and no one found it particularly unusual that Suharto meditated in caves and consulted astrologers and clairvoyants.

Both Sukarno and Suharto were leery of fervent Islam. Sukarno feared it could threaten the stability of his diverse, fragile country and at independence rejected the idea of making Indonesia an Islamic republic. Suharto kept his distance from the Arab Muslim world and for years kept Islamists at home on a short leash. Some went underground or left for more comfortable lives in neighboring Malaysia, which is also Islamic.

I told Professor Noon I didn’t understand how Muslim terrorists who had killed countless innocents in Indonesia and other countries could be considered martyrs. “Those who believe that have misinterpreted Islam,” he said. “The basic theme of Islam is love and affection. How can you put people who make bombs in paradise? Suicide bombers are not martyrs. They have lost the blessing of Allah, and they will receive His greatest punishment in the hereafter.”

Indonesia after Suharto’s fall was buffeted by drift, strife and communal conflict. Islamic extremists emerged from the shadows—and with them the country’s first suicide bombers. In Java, the island where Jakarta is located, mysterious assassins brutally killed scores of suspected black-magic sorcerers.

Meanwhile, between 1998 and 2004 three unlikely chief executives shuttled in rapid succession through the presidency—a millionaire engineer educated in East Germany, a nearly blind Muslim cleric, who often dozed off in meetings and was eventually impeached, and Sukarno’s daughter, whose most notable credential was her father’s genes.

Enter, in 2004, Susilo Bambang Yudhoyono, then a 55-year-old retired general who had been educated in the United States and who, as a youth, had sung and played guitar in a band named Gaya Teruna (Youth Style). He had a clean, graft-free reputation, a dedication to democracy and a belief that Indonesia’s traditionally tolerant, moderate form of Islam—Smiling Islam, Indonesians call it—was the true expression of the faith. The local news media referred to him as “the thinking general” and seemed delighted when, at a campaign stop in Bali, he sang John Lennon’s song “Imagine” in English. No one seemed to mind that it offered a distinctly atheistic outlook:

Imagine there’s no Heaven...
No hell below us...
And no religion too.
Imagine all the people
Living life in peace...

On September 20, 2004, some 117 million Indonesians voted in the largest single-day free election the world had ever seen to make Yudhoyono, who had promised to continue to reform the nation and the military and to rein in terrorism, the country’s sixth president. Five years later, he was re-elected in a landslide, collecting more direct votes (74 million) than any candidate had ever won worldwide. (The previous record had been Barack Obama’s 69 million votes in 2008.) In a nod to austerity, Yudhoyono’s second inauguration in October 2009 cost a mere $30,000.

Last year, Time magazine named Yudhoyono one of the world’s 100 most influential people. Not only has he continued with reforms to curb the military’s role in society, but he also struck a peace deal with anti-government rebels in Aceh province on the northern tip of Sumatra, ending a nearly 30-year war that had claimed 15,000 lives. Arrests, executions and raids had seriously weakened Jemaah Islamiyah (JI), a homegrown Al Qaeda look-alike considered Southeast Asia’s deadliest terrorist group. (The name means “Islamic Community.”) Freedoms have continued for the Chinese minority, numbering about five million people or roughly 2 percent of the population, who had become free to use Chinese characters on its storefronts, celebrate Chinese New Year and openly teach the Chinese language. “Things are more secure, much better. We’ll see,” said Ayung Dim, 57, a merchant who had survived the 1998 riots by hiding with his family in his metal shop before fleeing to Malaysia.

The Indonesian government also patched up relations with the United States. It laid the groundwork for the return of the Peace Corps, expelled four decades earlier by the anti-Western Sukarno, who taunted the American ambassador, Marshall Green: “Go to hell with your aid!” Yudhoyono threw his support behind an anti-corruption commission, which caught some big fish, including his own daughter-in-law’s father. Indonesia’s democratic transformation and political reform have brought about a resumption of military cooperation with the United States, which had been suspended because of the Indonesian Army’s abysmal human-rights record.

The day before Yudhoyono’s second swearing-in, I took a taxi to the English-language Jakarta Post to see how the media had fared under him and what had changed since Suharto, when insulting the president or vice president was a crime and newspapers could be closed after printing three objectionable articles.

The privately owned Post, one of 16 national newspapers, had recently moved into a sparkling new building. I was surprised to find an empty newsroom. I asked the editor, Endy Bayuni, where everyone was. “They’re out doing what reporters are meant to do—reporting,” he said. “There are no government restrictions any more, no issues we can’t report on. With all the corruption here, Indonesia is a gold mine for investigative reporters, but our reporters don’t have the skills yet to do that kind of reporting well because we weren’t allowed to do it for so long. We’re retraining them.”

“In the old days,” he went on, “we became famous as the paper you had to read between the lines to understand. We’d push the invisible line as far as we could. It was the only way to keep your sanity as a reporter. Every segment of society has a voice now, even if it’s an unwanted voice” like that of Islamic extremists.

One branch of Islam has resurfaced here in its hard-core, anti-Western jihadist form. The terrorist group Jemaah Islamiyah first captured the world’s attention in 2002 when a young suicide bomber with a backpack and a car loaded with explosives leveled two tourist bars, Paddy’s Pub and the Sari Club, on the Indonesian island of Bali. Over 200 people from 23 countries died. A marble memorial now marks the spot where Paddy’s stood, and a new bar has opened nearby with the name Paddy’s: Reloaded. In the next seven years terrorists launched several additional, deadly attacks—on restaurants in Bali and Jakarta, two at the JW Marriott and one each at the Ritz-Carlton and the Australian Embassy.

Though diminished by arrests and internal strife, JI and splinter terrorist groups still pose a big challenge to the fulfillment of Yudhoyono’s campaign promise that “God willing, in the next five years the world will say, ‘Indonesia is something; Indonesia is rising.’”

I met Nasir Abas in a dingy Jakarta coffee shop across the road from Cipinang Prison, which holds some of Indonesia’s toughest criminals and most incorrigible terrorists. Abas’ own terrorist credentials were formidable. He had trained on the Pakistan-Afghanistan border, set up a military academy in the jungles of the southern Philippines and taught half a dozen of the young men who carried out the first Bali bombing how to kill. His brother spent eight years in a Singapore prison for plotting a foiled terrorist attack. (He was released in January.) His brother-in-law was executed for his role in the bombing of Paddy’s and the Sari Club. Abas, 40, brought along a sidekick, Jhoni “Idris” Hendrawan, 34, who had taken part in three deadly terrorist attacks in Indonesia and been arrested while counting the money he had robbed from a bank to finance a future attack.

These days Abas has a new role: he works for the police. Abas helped officers question suspects responsible for the second Bali bombing. He has testified against JI operatives in court, leading to their conviction and imprisonment. His encyclopedic knowledge of the terrorist network provided authorities with a trove of intelligence. He is one of the first on the scene of terrorist attacks and often finds clues that only a JI insider would recognize. In his spare time he visits terrorists in Cipinang and other prisons, trying to convince them that killing civilians and innocents is un-Islamic. Some prisoners refuse to talk to him and call him a traitor; others, like Hendrawan, have bought into Abas’ deradicalization program and have forsworn violence. “I thought the students I trained would take part in jihad against forces occupying Muslim lands, like in Afghanistan,” Abas said. “Then the Bali bombing. This wasn’t jihad. Prophet Muhammad said it is wrong to do anything cruel, wrong to kill old men, women and children. After Bali, I came to realize many of my friends and relatives had strange ideas and thought it was OK to kill civilians.”

His conversion, he said, came after his 2003 arrest. “I always thought the police were my enemy.” But they called him Mr. Nasir and, after beating him the day of his arrest, never touched him again. If they had tortured him further, he said he would have been silent or given them false information. “They said, ‘We are Muslim like you. We aren’t against Islam. We just want to stop criminals.’ Even the Christian cops didn’t use bad words about Islam. I changed my mind about the police, and that was one turning point.”

Another, he told me, was when Cipinang’s commander came to see him in prison. “Bekto Suprapto was a colonel and a Christian. He told the ten men guarding me to take off my handcuffs. Then he told them to leave. I’m thinking, ‘What a brave man, because if I want to do something to him, I’m sure I could carry it off.’ We talked about jihad, about Christians and Muslims. He gave me a Bible and I ended up reading it. I started wondering why God hadn’t let me die or be killed. I answered my own question. He hadn’t because there was something God wanted of me. It was to do what I’m doing now.” Abas’ change of direction also had a practical benefit: it won his release from custody.

Abas—and mainstream experts on terrorism—say JI continues to recruit at its 50 schools and in the mosques it operates. But, they add, its leadership and structure have been severely weakened by Yudhoyono’s three-pronged strategy: first, to aggressively pursue terrorists, which has resulted in more than 400 arrests, several executions and the shooting death of JI leader Noordin Mohammad Top in 2009; second, to undercut the popular appeal of militancy by exposing it as un-Islamic; and lastly, to ensure that the government does not create more terrorists by treating prisoners brutally.

Recent elections offer a glimpse into the public’s changing attitudes. In parliamentary elections in 2004, Islamic parties won 38 percent of the vote; in 2009, the percentage dropped to 23. In a poll of Indonesians by a group called Terror Free Tomorrow, 74 percent said terrorist attacks are “never justified.” In another poll, 42 percent said religion should have no role in politics, up from 29 percent the previous year. Apparently, most Indonesians continue to embrace moderation and tolerance.

Indonesia’s ulema, or leading clerics, were long on the fence about terrorism, believing no Indonesians nor any Muslims could have been responsible for the attacks. Many never denounced the Bali bombing but did condemn a police raid in East Java in 2005 in which JI’s leading bomb master, Azahari “Demolition Man” Husin, was killed as a U.S.-trained counterterrorism unit raided his hide-out. Yudhoyono’s vice president, Jusuf Kalla, invited leading clerics to his house for dinner. He spoke with them for 50 minutes. He showed them pictures of huge stockpiles of bomb-making equipment and weapons the police had found at the hide-out. Then he showed them videos of young suicide bombers saying their goodbyes before heading out on death missions in search of martyrdom. “Do you still believe the police shouldn’t have raided the house?” Kalla asked. The clerics all agreed that the raid was justified. It was an important government victory to get influential opinion-makers on the record with a condemnation of terrorism.

“Indonesia has done far better than the United States combating terrorism as far as abiding by the rule of law goes,” said Sidney Jones, a longtime U.S. resident of Jakarta and a conflict analyst with the Belgium-based International Crisis Group. “There have been no witch hunts, no Guantánamos, no water boarding.” The Yudhoyono government, she said, treats terrorism as a law-and-order problem for the police, and the police in turn use what they call a “soft approach,” as they did with Nasir Abas. Everyone is charged in open court with reporters present. “Because of the information coming out of the trials, the Indonesian public became convinced that the terrorists are Indonesians, not CIA and Mossad operatives,” Jones said.

The Indonesia I visited this past October was a different country from the one I left a decade ago. Although 32.5 million of the country’s people still live below the poverty line, most Indonesians no longer wake up hoping they can simply make it through the day. The students’ agenda of the 1990s—democracy, civil order, economic opportunity, respect for human rights—had become the national agenda. Everyone I met seemed aware that Indonesia had been given something some countries never get: a second chance. The optimism was palpable. “If Indonesia were a stock, I’d be buying,” said Eric Bjornlund, co-founder of Democracy International, Inc., a firm in Bethesda, Maryland, specializing in international democratic development.

But many challenges lie ahead. Yudhoyono’s popularity rating remains high—75 percent in early 2010—but has fallen 15 percent since his election, partly because of scandals within his government and criticism that he is indecisive. What if it continues to fall and he alters course, back-tracking into the dictatorial ways of his predecessors? What about deep-rooted corruption, which has drawn protesters into Jakarta’s streets; inertia in the civil service; the gap between rich and poor; and the continuing battle for the soul of Islam between moderates and extremists? In 2009, Aceh province, for instance, adopted a new Shariah law (law of God) that calls for death by stoning for adulterers. To the relief of moderates, concerned about tourism and foreign investment, Aceh has yet to carry out any stonings.

One day, I sat with six students in the shade of a kiosk at Jakarta’s Paramadina University, which includes in its curriculum a course on anti-corruption. The two young women present wore colorful jilbabs, the Islamic scarf that covers the hair and neck. All six spoke excellent English. They wanted to know if I was on Facebook and what I thought of President Obama, who as this story went to press was planning a visit in March to Indonesia, where he lived with his mother and Indonesian stepfather from 1967 to 1971. He has become popular in Indonesia since his campaign and election, and this past December a 43-inch bronze statue was unveiled in a city park, depicting a 10-year-old Obama wearing schoolboy shorts with his outstretched hand holding a butterfly. (A protest campaign that began on Facebook, arguing that Obama is not an Indonesian national hero, succeeded in getting the statue removed from the park. Officials transferred it to Obama’s former school in February.) I asked the students what their goals were. One wanted to be a computer programmer, another an entrepreneur, a third wanted to study in the United States.

“For me,” said 20-year-old Muhammad Fajar, “the biggest dream is to be a diplomat. Indonesia can have a big place in the world, and I want to be part of it. But first we’ve got to show the world that Indonesia is not just about poverty and corruption and terrorism.”

David Lamb, who traveled Asia extensively as a Los Angeles Times correspondent, is a regular contributor to Smithsonian.