In 2011, most of Colombia’s 1.6 million foreign visitors didn’t veer off the Gringo Trail: the colonial Caribbean charm of Cartagena, the Edenic splendor of the Coffee Triangle, and cities like Medellín and Bogotá. But the number of annual foreign tourists is projected to reach four million by 2014. Is the rest of the country ready for its close-up? I’m curious to find out.

Today we’re starting with a hike to Caño Cristales, known as the River That Ran Away from Paradise. The waterway has reached near mythic status because of a plant called Macarenia clavigera. At certain times of the year, when the plant is in full bloom and the water flows over its tiny flowers, the river turns hallucinogenic shades of blue, red, yellow, orange, and green.

We land in the village of La Macarena, where Consuelo Ramos, a 22-year-old farm girl with a flawless French manicure, greets us. She has spent the past few years studying to be a guide for the local tourism association and walks us through her town of 3,500 inhabitants, where we pass kids playing soccer in the square, soldiers wearing combat fatigues and walking in formation, and silver-haired men sipping coffee at a sidewalk café.

Founded in the 1980s by farmers fleeing violence in Caqueta province, La Macarena exists because it’s where the farmers ran out of food. To survive, they picked fruit and carved out a life in the jungle. The Revolutionary Armed Forces of Colombia (FARC) quickly interrupted their peace.

Forty-nine years ago, the FARC started out as the self-proclaimed leftist voice of the poor. By most estimates, it has since become the largest drug cartel in Colombia. In 1998, to start peace negotiations with the group, then President Andrés Pastrana gave it a Switzerland-size piece of land, which included La Macarena, to create a zone that the Colombian army was prohibited from entering. The FARC settled in, recruited soldiers, and grew coca. In 2002, the military reclaimed the zone by force.

To get to the trailhead for Caño Cristales, we motor northeast for about a mile up the Guayabera River in a dugout canoe, then hop in a truck to drive a few miles over a rutted dirt road. When we arrive, I’m surprised to see a small convoy of vehicles, their drivers patiently waiting for visitors to return from the river. On the hike in, we pass a dozen Colombians on the sandy path and a swarm of yellow butterflies flitting in the direction of the Technicolor river. I count 25 vacationers splashing in the fresh pools and picnicking along the shore. Acevedo tells me that an average of 480 tourists per month, roughly 20 percent of them foreign, visit between June and November. Recently, the national airline, Satena, operated by the Colombian air force, started flying from Bogotá to La Macarena on weekends.

Given the area’s troubled past, the whole scene is surreal. But La Macarena is a showcase of sorts, a zone in the Colombian outback that the government, with heavy military reinforcement, has designated as a haven of responsible tourism to prove to the world that the country is finally outgrowing its very bad reputation.

Ramos serves us a wrapped banana leaf filled with fried plantains, rice, chicken, and potatoes, and tart lemonade. Then we take a swim. From the looks of these laid-back revelers, Colombians’ years of enforced solitude may finally be over.

“I’m not going to lie to you,” Acevedo later tells me. “The problems are still here. But we are finally free to go almost anywhere.”

In Colombia, however, freedom is a fickle concept.

IN 1991, WOOED BY Gabriel García Márquez’s Love in the Time of Cholera and the foolhardy antics of Jack T. Colton and Joan Wilder in Romancing the Stone, I signed up for a Spanish-language immersion program in Bogotá, unwittingly arriving at the apex of cocaine king Pablo Escobar’s power.

By the time of my visit, Escobar had declared “total and absolute war” on the government, according to Mark Bowden in his book Killing Pablo. Two years earlier, Escobar had attempted to assassinate presidential hopeful César Gaviria by blowing up an Avianca airliner, killing all 110 passengers on board. (Gaviria was not on the flight.) In Escobar’s hometown of Medellín, a sunny, mountainous metropolis that he turned into the most dangerous city on earth, Escobar paid local hit men $2,500 for each cop killed. He also blew up a Colombian police headquarters in Bogotá. In 1990, Escobar kidnapped Diana Turbay, a Bogotá TV news director and daughter of former president Julio César Turbay Ayala. (She was subsequently killed during a rescue operation.) Over the next two decades, abduction would become a primary political weapon and source of income and is still the most effective way for drug cartels and guerrillas to blackmail enemies.

I showed up in March of 1991. For seven weeks, I lived with a family in a gated middle-class Bogotá neighborhood, where an armed guard stood watch 24/7 at the end of the street. On weekdays I would hop a bus to class. On weekends my American and Colombian friends and I frequented mountainside discos, bused to outlying villages, and flew to the Caribbean beaches of Cartagena and Santa Marta. The violence was a bizarre abstraction; I knew it existed, but I never saw it. By the end of April, our professor, Mauricio Barreto, decided that it was too dangerous for us to remain in the country. I wasn’t ready to leave. Colombia was mysterious and sensual, from its mist-covered peaks to Fernando Botero’s fat sculptures to the sexy couples salsa dancing until dawn. On May 3, my last day in Bogotá, I wrote in my journal: “I know I’m coming back.”

When most people think of Colombia today, they still think cocaine, kidnappings, and guerrillas. In 2011, Colombia produced 760,000 pounds of cocaine. Farmers can sell a paste made from coca leaves, which is later processed into cocaine, for roughly $63,500 per pound. Cacao, the source of chocolate and one of the best alternative crops to grow, sells for 75 cents per pound. This is the very simple reason why, as Becerra told me, “as long as there’s a demand for drugs, there will be violence in Colombia.”

Much of the violence involves armed factions—guerrillas, like the FARC and the National Liberation Army, paramilitaries, and even the Colombian military—terrorizing local farmers for their land. Since 1985, more than 3.5 million Colombians, about 10 percent of the population, have been internally displaced. That statistic surpasses Sudan.

After Escobar was finally gunned down in 1993 by the Colombian military—with help from shadowy U.S. forces—the FARC took over the drug trade. Álvaro Uribe, Colombia’s president between 2002 and 2010, made it his priority to defeat the guerrillas, funneling money into the military. Between 2002 and 2006, homicides decreased by 50 percent, and they’ve been on the decline ever since.

In 2010, Juan Manuel Santos, President Uribe’s minister of defense, took office. With $5 billion in U.S. counterinsurgency aid, he pledged to finally end the five-decade conflict, pursuing peace talks with the FARC, whose numbers have dwindled from 17,000 in the 1990s to roughly 9,000 today. As of November, the first talks were held in Oslo, Norway. Every Colombian I spoke to was skeptical about the outcome, and their caution is warranted. Despite its denials, the FARC still holds captive an estimated 400 civilians and, according to the Colombian attorney general’s office, makes an estimated $2.4 billion to $5.5 billion annually from the drug trade and other illicit activities.

Still, 21 years after my first visit to Colombia, I decided that the time had come to return. There had been encouraging signs that the climate for travel had changed. In February 2012, the FARC posted a written statement online—albeit with machine-gun sounds embedded in the page—that it would no longer kidnap civilians. In April, when Cartagena hosted the Summit of the Americas, Barack Obama became the first president in U.S. history to overnight in Colombia. Paul McCartney even played a sold-out show in Bogotá.

Unfortunately, soon after I booked my flight, the FARC broke its promise and kidnapped a French journalist. I called my former professor to ask whether he thought the situation was really improving. Barreto, now a consultant for Caracol Television, which produces the hit show Pablo Escobar, Boss of Evil, was philosophical.

“The moment you start believing what the FARC says, you are in trouble,” Barreto told me. “The moment you start believing what the government says, you are in trouble. Always read between the lines in Colombia.” He gave a thoughtful pause, then continued, “Right now, the problem traveling here is not the guerrillas. The problem traveling in Colombia is because our roads are terrible.”

“THERE’S SOMETHING YOU HAVE to know,” Acevedo says, gunning his Subaru wagon to pass a gas truck as we begin the 425-mile drive from Bogotá to Medellín. “Colombians are crazy drivers. I’ll try to drive as civilized as possible. And that smell in the car? You don’t have to worry. I just put on new brakes.”

If you want to go off the beaten path in Colombia, it’s best to be with people you trust who have fresh information. It’s a bonus if they have good brakes. Given these criteria, Acevedo is the man for the job. Armed with two iPhones at all times, he’s in constant contact with friends and coworkers all over the country. Two years ago, he was hired as the incoming tourism manager for Voyage Colombia, a large operator, to bolster its eco- and adventure-travel itineraries targeting intrepid Dutch, German, Canadian, and Brazilian tourists. His new branch is one of only four or five outfits with countrywide coverage in Colombia.

“Ask any Colombian and they’ll say La Macarena is dangerous,” he tells me. “That’s why we’re looking for adventure travelers. But we only go to places the government guarantees there’s not going to be a problem.”

By the end of this 11-day journey via Cessna, horseback, tractor, Subaru, mountain bike, Twin Otter, and ocean outboard, Acevedo, photographer João Canziani, and I will have traveled a few thousand miles.

At the moment, we are climbing 11,000 feet over the Cordillera Central, then dropping into Armenia, the heart of Colombia’s mountainous Coffee Triangle. We’ll spend a night at Hotel Bambusa, a peaceful hacienda on a cacao plantation exquisitely renovated by its artist owner, Santiago Montoya. The next morning, we’ll drive to Los Nevados National Park, where we’ll hike in the Cocora Valley under 260-foot wax palm trees before driving to an evening tutorial in coffee making at Hacienda Venecia. The century-old coffee farm sits on 495 acres nestled in the volcanic hills below Manizales, home to some of the best mountain biking in Colombia. There’s no time to ride, though: we’re driving on to Medellín in pursuit of yet another incredible network of trails.

The next morning, we meet Acevedo’s friend, Alejandro Puerta, a 40-year-old production engineer, mountain biker, and, according to his friends, technology nerd. In the past few years, he’s used Google Earth to scout an estimated 200 mountain-biking routes all over Colombia. His most epic ride topped out at 15,750 feet on the Nevado del Ruiz volcano.

“I try every week to never repeat the same path,” Puerta says.

Today, Puerta, his 38-year-old girlfriend, Mildred Uribe, and friend Carlos Carvajal, a 42-year-old mechanical engineer who just finished circumnavigating South America by bike, are taking us mountain biking on a favorite 20-mile route that follows the Cauca River, north of Medellín, and will end with a feast in Santa Fe de Antioquia, a 16th-century whitewashed colonial town with red-tile roofs and seven churches. On our right are the dry peaks of the Cordillera Central, with the Cordillera Occidental to the left. The smooth single- and doubletrack passes fruit orchards and a cluster of expensive-looking vacation homes before passing over a 400-year-old colonial bridge.

“Ten years ago I couldn’t do this trip,” Puerta says. “We were completely kidnapped inside Medellín. It was terrible.” He is speaking figuratively, but his family experienced horrific violence firsthand, and he dislikes discussing the past. “I don’t want people to be afraid to come to Colombia,” he says. “It’s not all drugs. It’s not all bad things.”

The country’s extreme makeover is especially evident in Medellín. In 1991, the city, with a population of two million, had a murder rate of 7,081. That same year New York City, with four times the population, had roughly 2,200 murders. Today, Medellín has grown to 3.8 million people; it isn’t crime-free, but homicides were reduced to 1,528 in 2011. (By comparison, New York City had 515.) Plus, as Carvajal tells me, its potential for cycling and mountain biking is enormous. On the last Wednesday of every month, he arranges, via social media, La Fiesta de la Bici, a non-competitive ride that draws an average of 5,000 cyclists.

That evening, as Acevedo accelerates around the curves on the hour-long ride back to Medellín, the moon illuminates the twinkling lights below. As we reach the outskirts of the city, we pass a strip of drive-in lodges with names like Motel Sensaciones and the famous Metrocable, one of two gondolas that provide transportation from the poorest hillside barrios to the city. This gondola, along with a 1,300-foot escalator up another mountain, is connected to a high-speed light-rail system, which allows people in the barrios a way to get to work, reducing crime by more than 50 percent.

Later in the week, we ride the Metrocable at 8 p.m. on a Friday. The city smells like roses and mani, sweet roasted peanuts sold by street vendors. It’s the eve of the famous Fiesta de las Flores, an annual weeklong party where growers transform Medellín into a garden, erecting brilliant flowery sculptures in every public space available. I watch the Virgin Mary miraculously materialize out of carnations, her image seeming to soothe the country’s slowly diminishing post-traumatic stress disorder.

AFTER MORE THAN A week of non-stop travel, we’re all ready for the tranquilovibe of a beach. We’re heading to the central Pacific coast, known to have the best surf in Colombia and also an excellent place to see migrating humpback whales.

“The conditions are so good for nature here that it grows everywhere,” says Guillermo Gómez, co-owner of El Cantil Ecolodge, an Eden on the edge of Chocó, Colombia’s poorest region.

A former businessman from Medellín, 45-year-old Gómez is wearing flip-flops, boardshorts, and a Billabong baseball hat and has the ripped physique of a surfer. As the crow flies, his eco-lodge is 120 miles from Medellín. But because it’s accessible only by boat and backs up to one of the thickest jungles in the world, El Cantil might as well be a million miles away. To arrive there we flew into Nuquí, a relaxed village with no roads to the outer world, founded by escaped slaves nearly 200 years ago. Then we motored an hour south down the Pacific coast in an outboard panga.

“The reason the slaves came here,” Gómez says, “is that nobody was going to find them.”

Drug cartels infiltrate the area for the same reason. Last July, Colombian police seized 388 pounds of cocaine at a covert lab near a beach in Ensenada de Utría National Park, less than 20 miles from El Cantil.

“The cartels aren’t interested in making problems for tourists,” Gómez reassures me. In the 20 years Gómez and his family have owned their property, they have had very few security problems. Gómez’s lodge has such an impressive safety record that when Uribe was president, he called Gómez looking for trustworthy, on-the-ground advice.

To crack down on the cartels, Uribe sent army intelligence officers to infiltrate nearby villages and weed out locals who act as liaisons to the drug runners. These days the cartels keep to themselves, and curious travelers from all over the world are attracted to El Cantil by its stunning location, fresh Chocóan meals, and chicpalafitos—clean, rustic, oceanside cottages lit by oil lamps and strung with hammocks. This week a high-level international-development worker from the U.S. and his 17-year-old son are here to surf; a Dutch real estate lawyer, his wife, and two teenage daughters came to watch migrating whales; a professor of Latin American history from New York City is here with her two kids to relax before school starts; and a young Australian mining executive and his Colombian girlfriend are taking a romantic break from Bogotá.

“It’s actually nice to harbor the illusion that people shouldn’t come here,” the U.S. aid executive told me as he and his son played cards in the open-air dining room. “Six months ago, my security team told me, ‘No, you can’t go to Chocó.’ I convinced them that if there’s a problem, the local commandante knows I’m here. I’ll just call the police. They know everything that’s going on.”

Once again, Colombia isn’t living up to its deadly reputation. What I’m seeing in front of me is paradise—the turquoise Pacific, black-sand beaches, and so much greenery that even the volcanic boulders sticking out of the ocean are covered in ferns and sprouting palm trees.

What are the odds of a catastrophic mishap for a traveler veering off the beaten path? The answer depends on who you ask and where you are. Even the State Department travel warnings tend to flip-flop: “Security in Colombia has improved significantly in recent years,” but “terrorist activity remains a threat throughout the country.” An unexpected result of the violence, however, is that most Colombians, perhaps by psychological necessity, crave peace and go out of their way to ensure that foreigners experience it while on their soil.

“Pablo was a real monster, but I chose the right path for me faster because I saw that violence,” Gómez told me at dinner one night. “What’s going on with this country makes us go deeper.”

To attract more tourists, Termales, a fishing village roughly three miles south of El Cantil, has capitalized on what is literally its hottest asset: a sulfur spring. Using government funds, the people of Termales built a jungle spa with mud baths, decks overlooking a river, and beautiful concrete pools. When we arrive, a group of 10 Germans in Speedos are soaking in the springs.

Back at El Cantil, guests gather for a lunch of fresh tuna, coconut rice, fried plantains, and frosty Aguila beers. I nap in the hammock, then borrow a stand-up paddleboard from Gómez’s wife, Adriana. It’s late afternoon, and the water is choppy. I fall headlong into the salty waves a few times before I sync up with the ocean. Finally, I find my balance and paddle toward the sunlight.

Contributing editor Stephanie Pearson wrote about fitness mogul Bahram Akradiin September.