In 1811, the Colombians first declared their independence. Eight years later, with the help of Simon Bolívar, the country was theirs. But afterward, Cartagena's prominence began to decline. The new port city of Barranquilla, less than a hundred miles to the northeast, overtook it economically. During this time, the upper class abandoned the city for the open spaces of nearby Manga Island. Some of their former mansions and palaces would remain empty for more than a century, moldering in the humidity. The old city became old for the first time.

The next century brought fits of renewal, but this wasn't always for the good. In the sixties and seventies, Cartagena tried to take Havana's place as the jet-set's Caribbean playground: Discos and casinos opened; city promoters started a film festival; the Miss Colombia pageant was held annually by the Hilton's pool. But for the most part, developers turned their backs on Cartagena's history, building a new neighborhood of concrete condos and hotels in Bocagrande, a spit of land southwest of the old city.

Meanwhile, the historic center languished. Many of the mansions, convents, and monasteries were carved into apartments, boardinghouses, offices, and storage spaces. There were exceptions, of course—the old Santa Clara convent was turned into a luxury hotel long before the current wave of renovation—but as a friend who grew up in Cartagena tells me, twenty years ago there were few shops, restaurants, or people in the old town. "Only your dad went down there," he says, "and then only to go to work."

The party in Bocagrande continued until the early 1980s, when guerrillas and drug lords from the Andean lowlands and the Pacific coast escalated their feuds with the federal government into all-out civil war. Soon, Colombia became one of the most dangerous countries in the world, according to U.S. State Department travel advisories. Except for the lonely Lonely Planeter, international tourism came to a halt. Conventional wisdom held that Cartagena was about to enter another period of neglect and languor, but that would prove to be wrong.

In 2002, the Colombians elected Álvaro Uribe president on his platform of returning law and order to the country—a promise he has mostly made good on, thanks to billions of dollars in U.S. military support. (President Bush considers Uribe his strongest ally in left-leaning South America.) In four years, Uribe's right-wing government has managed to mostly contain the political violence to isolated inland regions; with a few exceptions, it is no longer a part of daily life in Bogotá, Medellín, Cali, and other major cities. Travelers still need to take precautions, but foreign tourists are beginning to return, and for many, the first stop is Cartagena.

The best way to get to know Cartagena is to do what Willy and I did for several days—simply wander around. The historic city is divided into three neighborhoods: El Centro, where you'll find the major churches, museums, and plazas, and where the nobility once lived; San Diego, an upscale residential neighborhood formerly occupied by wealthy merchants and top military officers; and Getsemaní, traditionally home to Jews, Muslims, blacks, Indians, gold- and silversmiths, and low-ranking military officers. El Centro has seen the most renovation, Getsemaní the least, which makes it, in some ways, the most interesting for strolling. In the mornings, the streets smell of dust, sun, and motorcycle exhaust. In the afternoons, the salty trade winds blow through the palm fronds and ferns, and the air smells damp and leafy.