The Colombian experience with labor market reform that began in 1990 and ended with the issuing of a new labor code in 2002 provides important lessons about the difficulties of implementing policy changes. A successful reform has to surpass a set of "deals," during the design phase, consensus building with civil society, submission to Congress and parliamentary debate, before it gets approved. The paper presents the story of two failed attempts by the Colombian government to produce these "deals." It shows what economic and social considerations created the need for reform, describes the actual policy changes implemented and evaluates their impact. The paper delves deep into the political aspects of the reform effort.