In 2000, the 26-year-old Bedoya was working with Ignacio Gómez at the Bogota daily newspaper El Espectador, covering the Colombian war against terrorism. At the time of her abduction, she was investigating a story on arms trafficking by both state officials and the far-right paramilitary group United Self-Defense Forces of Colombia (AUC). On 25 May, she visited La Modelo prison in Bogota, where she had been promised an interview with a paramilitary leader known as "the Baker". Suspecting a possible trap, she brought along an editor and photographer from El Espectador's staff, but when the pair were separated from her for a moment while awaiting clearance to go into the prison, she disappeared.
Bedoya was seized, drugged, and forced into a car by three men. Her attackers drove her to a location several hours away, where they tortured and raped her. According to Bedoya, the men identified themselves as working for paramilitary leader Carlos Castaño. The kidnappers insisted that Bedoya "pay attention" as they raped her, telling her, "We are sending a message to the press in Colombia." They also threatened her colleague, stating that they "planned to cut Gómez into tiny pieces"; Gómez would flee the country six days after the attack. Bedoya was left tied up in a garbage pile near a road, and when she crawled out, she was discovered by a taxi driver.
The case was stalled for more than a decade with the Colombia Attorney General's office before Bedoya appealed it to the Inter-American Commission on Human Rights. In May 2011, a paramilitary soldier was arrested and confessed to being one of Bedoya's three attackers.
In 2001, Bedoya was hired by El Tiempo and was put in charge of its law enforcement coverage, including reporting on paramilitary groups. In early August 2003, she traveled to the town of Puerto Alvira to report on how it had been taken and held by the Revolutionary Armed Forces of Colombia (FARC) for more than a year, forcing its 1,100 inhabitants into full-time cocaine production. The leader of the FARC guerrillas ordered the kidnapping of Bedoya and her photographer immediately on their arrival, stripping them of their cameras and clothing. Though the FARC leader had ordered that the journalists not be spoken with or fed, women of the town continued to bring them food. The townspeople tried without success to alert the Red Cross to the pair's abduction, and a local priest warned them that the guerrillas were planning to take them into the forest and murder them. After the townspeople alerted the regional FARC commander to the situation, however, the journalists were quickly freed. The commander offered to reimburse them for their lost time and equipment, but Bedoya and the photographer refused. On her return, Bedoya filed a story on living conditions in FARC-controlled territory, being careful not to incriminate any of the townspeople who had aided her.
In November 2010, Bedoya released her book Vida y muerte del Mono Jojoy about Víctor Julio Suárez Rojas, better known as "Mono Jojoy", a FARC leader who had recently been killed. The book alleged that Mono Jojoy had issued an assassination order against Caracol Radio journalist Néstor Morales. In response, the FARC-aligned news agency Noticias Nueva Colombia posted a headline on its website accusing her of being a military intelligence agent, causing the Colombian-based Foundation for Press Freedom and Canadian Journalists for Free Expression to issue statements of concern for her safety.
As of November 2011, Bedoya continues to work as a journalist for El Tiempo. For security, the Colombian government has assigned her three bodyguards as well as a bulletproof car.
In 2000, Bedoya was awarded the CJFE International Press Freedom Award, sponsored by the Canadian Journalists for Free Expression. In 2001, Bedoya was awarded the Courage In Journalism Award of the International Women's Media Foundation. The award was "big news" in Colombia, raising Bedoya's profile and leading El Tiempo to hire her away from El Espectador. She later described the award as "one of the things that kept me going" after the first attack.
In 2012, Bedoya was awarded the International Women of Courage Award.
In October 2016 it was announced that RAW in WAR was awarding its annual Anna Politkovskaya Award to Bedoya. She received the award in London on 11 March 2017, at a ceremony during the Women of the World Festival at the Southbank Centre.