Si on doit dater Koléa, c'est sans doute à l'époque turque qu'il faut ramener sa fondation. C'est Hassan Ben Kheïrdine qui aurait fondé la ville en 1550, pour servir de refuge aux musulmans chassés d'Espagne par la reconquête chrétienne. Les premiers habitants devaient donner à Koléa un cachet particulier. Artisans et hommes de culture vont en faire une ville où il faisait bon vivre. Des juifs, chassés également d'Espagne, devaient les rejoindre, apportant également leur savoir-faire. Des Algériens, venus de différents coins du pays, vont également s'y installer. On y pratiquait différentes activités, notamment le tissage de la soie, ainsi que l'agriculture, rendue possible par l'abondance de sources. Aujourd'hui, l'arbre fétiche est le néflier (zaârour) dont une fête est organisée chaque année au printemps. Les Français s'emparent de Koléa en 1831. la résistance est menée par Mohammed ben Allal. Il est emprisonné par Rovigo, puis libéré par l'Emir Abdelkader qui en a fait son lieutenant. Les Français, contrairement à ce qu'ils disent, ont trouvé une ville florissante. Voici par exemple ce qu'en dit le guide Quentin, en 1948 : «Les eaux sourdent de toutes parts, abondantes et pures, dans le petit vallon de Koléah, elles sont distribuées avec art pour arroser de magnifiques vergers d'orangers, de citronniers, de grenadiers et, en général, les jardins qui entourent la ville sont couverts de tous les arbres à fruit de l'Europe.»
