In 1955 the club won their first national championship under the coaching of Argentine captain Guillermo Coll, in that era the club became known by the nickname millonario (Millionaire) because of their ability to attract top class footballers.
In 1978 the club won their second league title, this time the team was led by Chilean captain Elías Figueroa. In this campaign they set a new record in the domestic tournament, for the number of games unbeaten and soon won the Copa Chile to claim the league and cup double.
In 2004 the club became a registered company, but the change of status did not bring the expected improvement in results. In 2006 they finished in 18th place out of 20 teams, forcing them to face a playoff against Fernandez Vial to keep their place in the top flight. Ultimately the club would triumph thus preserving their spot within the Chilean first division.
The club made a surprising run to the final of the Clausura 2008 tournament, where they lost to champions Colo Colo. Following this success, the club intends to float on the Chilean and Palestinian stock exchanges.
In January 2014, Palestino was fined the equivalent of $1,300 for using a new team jersey with the club's traditional colors, red, green and black, and with the number one shaped as the map of Palestine before the creation of Israel. Chilean Jewish groups complained, with a formal complaint to their national Federation being made by Patrick Kiblisky, owner of first-division club Ñublense. The jerseys were said to have been first used in December 2013, although the club said they were used in the prior season. The federation banned the shirts and fined the club by the grounds that the Federation is opposed to "any form of political, religious, sexual, ethnic, social or racial discrimination". On its Facebook page, the club stated: "For us, free Palestine will always be historical Palestine, nothing less."