News of a Kidnapping—like any new work by García Márquez—received a great deal of attention when it was first published in Spanish in 1996, and the following year, in English. A welter of reviewers focused their attention on the myriad aspects of the book: its style, the events it depicted, the state of affairs in Colombia, the drug wars. While this book was a marked departure from the magical realism that characterizes García Márquez's fiction, few reviewers found this to be cause for complaint. The dramatic events that García Márquez has to work with easily provided what John Bemrose called in Maclean's, "thriller-like momentum." Indeed, as Michiko Kakutani pointed out in The Houston Chronicle, García Márquez "uses his novelist's instinct for emotional drama to give the reader a wonderfully immediate sense of his subjects' ordeal: their spiraling hopes and fears, their fantasies of escape, their desperation and despair." She was not alone in comparing this book to García Márquez's "most powerful fiction." R. Z. Sheppard's commentary in Time that News of a Kidnapping "brings together the world's two best-known Colombians, symbolically locked in a struggle for their nation's soul"—García Márquez and Pablo Escobar—illustrates the inherent narrative power of this non-fiction story.

García Márquez started out his career as a journalist, winning important prizes in that field, and reviewers noted that his skill had not lapsed. Wrote Sheppard, "One can almost hear García Márquez asking, Who? What? Where? When? and Why? on every minutely detailed page." Page also pointed out that the "terse" style of the book "reflects a conscious choice to let the hostages tell their own stories without impressing upon them the stamp of García Márquez's imagination.''

Reviewers, however, also noted that the fantastic elements of the crime, and the drug wars in general, brought the book closer to García Márquez's magical realism. Colombia presents a world hardly imaginable for most American readers, a world where law enforcement officers, Congressional representatives, and journalists are gunned down at the will of criminals. As Robert Stone challenged readers of the New York Times Book Review, "[L]et us imagine that we have a President who carries five bullets in his body as the result of an assassination attempt by drug traffickers. Let us imagine that Lady Bird Johnson and Amy Carter have both spent time in the hands of kidnappers." As Kakutani pointed out, books like News of a Kidnapping remind the reader that the "magical realism employed by García Márquez and other Latin American novelists is in part a narrative strategy for grappling with a social reality so hallucinatory, so irrational, that it defies ordinary naturalistic description."