Tayrona National Park -- a tropical unspoilt beach paradise, with overnight options ranging from expensive eco lodges to beachside hammock rentals.
Magdalena is easily one of Colombia's most visited regions, as it is home to the ever popular port and tourist hub of Santa Marta. Santa Marta also serves as the jumping off point for virtually anything further east, including the (in)famous Ciudad Perdida trek, the Sierra Madre mountains, the beautiful beaches of Tayrona National Park, and onwards to Riohacha and Cabo de la Vea in Colombia's northernmost department, La Guajira.
Magdalena is also most infamous for the Banana Massacre. As Colombia's principal and very productive banana-growing region, the department swelled with workers for the one-time banana empire of the United Fruit Company. The incoming migrant workers, pejoratively dubbed "fallen leaves" to equate them with rubbish, worked under conditions that would not be tolerated in the modern era, and indeed were not tolerated then--the workers organized an enormous strike, demanding written contracts, eight-hour days, six-day weeks and the elimination of food coupons. The Colombian government, in part fearful of a U.S. military intervention to protect "its interests," decided to dispatch an army regiment to Ciénaga, with orders by General Cortés Vargas to end the strike by all means necessary. Having set machine gunners on the rooftops of the main square, surrounding the strikers, the army issued a five minute warning and then opened fire on the assembled workers, along with their families. Hugely important to Colombian history, the massacre was followed shortly by the civil war known as La Violencia, and to this day, anti-government militants such as the FARC point back to this day as the beginning of their cause.
In a far less violent manner, Magdalena is further important to the history and culture of Colombia for having reared one Gabriel García Márquez. Born and raised in Aracataca, he became Colombia's and one of Latin America's greatest and most respected authors. "Gabo" drew upon his personal history in the region extensively in his literature, basing the fictional town of Macondo on his own hometown, and creating a fictional version of the Banana Massacre in his most well-known novel, One Hunded Years of Solitude.
Despite being by far one of the country's top tourist destinations, Magdalena has some serious problems. Narco-traffickers, paramilitaries, and even FARC militants are present in the area, most notoriously in the Sierra Madre mountains, but attacks on civilians do occur in the cities, where business owners are routinely forced to pay extortion money to the paramilitaries. Less exotic crimes-of-opportunity, such as backpacker muggings on forest trails, are nonetheless a more realistic concern to travelers. As a rule, foreign governments advise against travel in the countryside, especially into the mountains (and this very much does include the nevertheless-popular trek to Ciudad Perdida). The main roads are well policed, though, so you should rest easy traveling along the coast, or down the road towards Aracataca and Fundación.
If riding a motorcycle, there is one weird problem to be wary of along the main coastal road to the west of Ciénaga--beggars/bandits pulling a rope across the road, forcing motorcyclists to either stop and pay up, or be sent flying. Motorcyclists should a) reconsider whether motorcycle travel is a great idea in Colombia, and b) ride alongside a large vehicle, such as a truck or inter-city bus, which will force the kids to drop their rope.
The clear next destinations from Magdalena lie to the east, along the coast of La Guajira, or to the west, to the big cities of Barranquilla and Cartagena.