Kólia vznikla pravdepodobne z pôvodných anglických a škótskych pastierskych psov. Odkiaľ pochádza ich dnešný názov nie je dodnes celkom jasné. Podľa niektorých pásli tieto psy plemeno ovcí s čiernymi hlavami a nohami „Col“, psy boli teda nazývané „colley dogs“. Podľa iných teórii pochádza ich názov zo slova „coaly“ čo znamená čierny ako uhoľ.

Prvé zmienky o psoch nazývaných Colleys pochádzajú už z 18. storočia, ale plemeno nemalo ešte ani zďaleka dnešnú podobu, boli to hrubšie a ťažkopádnejšie psy. Neskôr k nim bol pravdepodobne prikrížený írsky a Gordonov seter, tiež barzoj, čím kólia získala elegantnú pretiahnutú hlavu. Prvé kólie boli predovšetkým trikolórne alebo blue-merle, najznámejšia dnešná farba – zlatá sa presadila až neskôr. Až do polovice 19. storočia bolo však plemeno málo známe. Od roku 1859 sa v Anglicku konali prvé výstavy psov a čoskoro sa na nich objavili i prvé kólie, z ktorých len máloktoré boli uznané ako čistokrvné.

V roku 1868 sa objavila najvplyvnejšia kólie tej doby zlatý Old Cockie, ktorý sa dožil 14 rokov a výrazne prispel k zušľachteniu kólii. V roku 1876 sa preslávil Mr. S. E. Shiley so svojou trojicou kólii – Hulakin, Honpipe a trikolórny Trefoil. Maude, dcéra Old Cockieho bola nakrytá Trefoilom a z tohto spojenia sa narodil Charlemange, veľmi známy šampión, zásluhou ktorého sa uplatnila zlatá farba s bielym golierom. Tieto psy sa stali základom plemena a v tých časoch boli súčasťou každej slávnej chovateľskej línie. Takmer každá dnešná kólia má pôvod v Charlemangovi a teda aj v Old Cockiem a Trefoilovi.

V tomto čase sa kólie stali miláčikmi kráľovnej Viktórie, čo napomohlo popularite plemena. Do Ameriky boli prvé kólie vyvezené z Anglicka už koncom 19. storočia. Bohatí Američania platili množstvo dolárov za anglické kólie a tak nečudo, že množstvo kvalitných kólii bolo predaných práve do Ameriky.

V strednej Európe (teda aj na území Slovenska) sa prvé kólie objavili ešte za čias Rakúsko – Uhorska, pred prvou svetovou vojnou. Tieto psy však plnili svoje pôvodné poslanie – pasenie oviec a len málo sa hľadelo na ich výzor. Po prvej svetovej vojne z nich zostalo len niekoľko jedincov. Niekoľko chovateľov sa ich „zozbieraním“, ale i importom ďalších kólii podarilo dostať plemeno z najväčšej krízy. Podobná situácia nastala aj po druhej svetovej vojne. K väčšiemu rozšíreniu kólii aj na našom území došlo až po uvedení filmu „Lassie sa vracia“. Prvé snahy o založenie klubu, združujúceho chovateľov boli už v rokoch 1924 a 1936, no klub vznikol v Československu až v roku 1947. Odvtedy bola budúcnosť plemena zaistená. Odvtedy prešlo mnoho zmien a výsledkom je, že v dnešnej dobe na Slovensku pôsobí stály Klub chovateľov kólií a šeltií.