Paletta debutó en primera división en el año 2005, jugando para el Club Atlético Banfield. Disputó la Copa Libertadores de América, ingresando en octavos de final, tras un cambio en la lista de buena fe, debutando frente al equipo colombiano Deportivo Independiente Medellín. Tuvo un buen debut y su equipo progresó en la copa, hasta los cuartos de final, donde fueron eliminados por River Plate.
La buena actuación de Paletta en la competición llamó la atención de los dirigentes del club inglés el Liverpool. Liverpool pagó 2 millones de euros por el pase del jugador, quien firmó por cuatro años el 4 de julio de 2006. Debutó para el Liverpool en un partido amistoso contra el Wrexham, ganando por 4-3. Tras muchos partidos como suplente, en la liga, jugó el encuentro frente el Arsenal, con el que sufrió la goleada por 6-3, a partir de ese partido se empezó a decir que Paletta todavía era inexperto para el fútbol inglés, por lo que, después de un año, volvió a Argentina para jugar en Boca Juniors, en un intercambio entre el 50% de su pase y el de Emiliano Insúa. Sin embargo, ya en el equipo argentino, demostró un excelente nivel de juego, pasando a ser referente en la defensa.
Estas actuaciones le valieron la convocatoria por parte de Sergio Batista para formar parte del plantel de la selección que disputó los Juegos Olímpicos de Pekín 2008. Pero por pedido de Boca Juniors que ya había cedido a Juan Román Riquelme y Fabián Monzón pidió a la Asociación del Fútbol Argentino no tomarles más jugadores ya que debían afrontar la Recopa Sudamericana, el torneo local y la Copa Sudamericana. El 11 de noviembre de 2008 sufrió una de las peores lesiones: la rotura de los ligamentos cruzados. Esta lesión lo mantuvo afuera de las canchas en un plazo mínimo de seis meses. El 30 de junio de 2010, volvió al fútbol europeo llegando libre al Parma Football Club por tres temporadas. El 2 de febrero de 2015 se hizo oficial su traspaso al A. C. Milan a cambio de 3 millones de euros y firmando por 3 temporadas. En 2018 tras terminar su vinculación al elenco milanés, y coquetear con su vuelta a Boca Juniors, terminó llegando al fútbol chino para jugar en el Jiangsu Suning de la Superliga de ese país.
Tras rescindir su contrato con el conjunto chino en agosto de 2019, el 6 de noviembre del mismo año regresó a Italia para jugar en la A. C. Monza. Con este equipo consiguió ascender a la Serie A antes de marcharse en febrero de 2023.
Ha sido internacional con la selección de fútbol de Italia en 3 ocasiones. Debutó el 5 de marzo de 2014, en un encuentro amistoso ante la selección de España que finalizó con marcador de 1-0 a favor de los españoles. El 13 de mayo de 2014 el entrenador de la selección italiana, Cesare Prandelli, lo incluyó en la nómina preliminar de 30 jugadores convocados para la Copa Mundial de Fútbol de 2014. Fue confirmado en la lista definitiva de 23 jugadores el 1 de junio.
.jpg)
Italia
