Le club est fondé le en participant à une compétition "coloniale" (de différentes communautés d'immigrés) à Osorno. Il est créé par un groupe d'immigrants palestiniens, le nom du club reflète l'origine de cette communauté installée au Chili. En 1952, la Fédération du Chili de football met en place les premières ligues professionnelles. Palestino est accepté en deuxième division, qu'il gagne aussitôt et est donc promu pour la Primera División 1953.
En 1955, le club remporte son premier championnat national sous la houlette de son capitaine argentin Roberto Coll(es). À cette époque, le club est connu sous le surnom de Millionaire en raison de leur capacité à attirer des footballeurs de haut niveau.
En 1978, le club remporte son deuxième titre de champion, l'équipe est dirigée par le capitaine chilien Elías Figueroa. Au cours de cette campagne, ils établissent un nouveau record dans le tournoi national pour le nombre de matches sans défaite. Durant cette décennie, le CD Palestino enrichit par ailleurs son palmarès en gagnant la Coupe du Chili à deux reprises, en 1975 et 1977.
Après de nombreuses années sans résultats probants, le club dispute (et perd) la finale du championnat de clôture2008[5].
Le , en raison de son caractère discriminatoire, la fédération de football du Chili décide d'interdire le nouveau maillot du club dont le chiffre "1" représente la carte de la Palestine mandataire avant la création de l'État d'Israël[6].