Horas después de la ceremonia de posesión de Uribe, como parte de una de sus promesas de campaña, el ministro del Interior y de Justicia Fernando Londoño Hoyos radicó en el Congreso un proyecto de ley para convocar a los colombianos a votar en un referendo contra la «politiquería». Se trataba de dieciséis puntos en los que se buscó reducir el gasto público y la burocracia estatal con la eliminación de los auxilios parlamentarios, las suplencias para cargos de elección popular e incluso las contralorías departamentales y municipales, así como las personerías. La iniciativa también buscó congelar los honorarios de los expresidentes, diputados y concejales. Además, pretendía impedir que las personas condenadas por delitos contra el patrimonio público pudieran aspirar a cargos de elección popular. Asimismo, presentó la idea de reducir el Congreso a una sola cámara y otorgar curules para grupos armados por vía presidencial.
El texto se moderó en sus objetivos a principios de julio de 2003, con el fallo de la Corte Constitucional, que declaró inexequibles varias de las propuestas del referendo. Estas evidenciaron que, tras haber ganado con creces la primera vuelta presidencial, Uribe buscaba cambiar la arquitectura del Estado para concentrar más atribuciones en el Poder Ejecutivo y someter a la clase política tradicional, lo que le ocasionó roces con sus propios partidarios en el Senado y la Cámara de Representantes.
El 25 de octubre de 2003 los colombianos fueron llevados por primera vez en la historia a votar un referendo, luego de que esta figura fuera reglamentada en la Constitución de 1991. El referendo fracasó por falta de votos, la clase política no lo respaldó y los maestros, que vieron sus pensiones de jubilación en riesgo, se movilizaron masivamente para votar en contra.