De los 18.712 habitantes, Palestine estaba compuesto por el 62.13% blancos, el 23.28% eran afroamericanos, el 0.54% eran amerindios, el 0.89% eran asiáticos, el 0.06% eran isleños del Pacífico, el 10.37% eran de otras razas y el 2.73% pertenecían a dos o más razas.