Palacios debuteerde in 1997 in het Colombiaans nationaal elftal en speelde 10 interlands, waarin hij 1 keer scoorde.[1] Onder leiding van bondscoach Hernán Darío Gómez maakte hij zijn debuut op woensdag 30 april1997 in de WK-kwalificatiewedstrijd tegen Peru (0-1) in Barranquilla. Hij trad in dat duel na de eerste helft aan als vervanger van Osman López.