Vanhimmissa asiakirjoissa paikkakunnan nimi esiintyy muodossa Karlabi, josta Kokkolan ruotsinkielinen nimi Karleby on muodostunut. Suomenkielinen nimi Kokkola tulee mahdollisesti Kokkolahti -nimestä. Kokkolahdeksi kutsuttiin lahtea, joka työntyi mereltä sisämaahan aina Kirkonmäelle saakka. Tarinan mukaan lahden suurilla kivillä istuivat kokot eli kotkat.
I de äldsta dokumenten skrivs ortens namn Karlabi, vilket gett upphov till dagens svenska namn Karleby. Det finskspråkiga namnet Kokkola kan möjligen härledas ur namnet Kokkolahti. Viken som stack in från havet ända till Kyrkbacken kallades nämligen Kokkolahti. Enligt historien satt det örnar (fi. kokko eller kotka) på vikens stora stenar.
Redan under medeltiden fanns det hamn, skeppsbyggeri och handelsplats i Gamlakarleby. Landhöjningen har spelat en central roll i stadens historia. Landhöjningen har nämligen format omgivningen avsevärt och påverkat bl.a. utvecklandet av hamnverk och handel. Handel bedrevs längs Bottenvikens kust och även jordbruk, jakt, fiske och säljakt var viktiga näringar.
Tjärhandeln, som kom att bli mycket viktig i Gamlakarlebys historia, började redan på 1500-talet. Då utkämpades också Nordens sista betydelsefulla bondeuppror, klubbekriget. En del av händelserna i klubbekriget utspelade sig i Gamlakarleby.
Den 7 september 1620 undertecknade Sveriges konung Gustaf II Adolf ett dokument som ledde till att den lilla jordbruks- och fiskebyn Ristrand blev en stad med namnet Gamlakarleby. Nuvarande stadssundet var på den tiden en smal havsvik som ledde ända till Kyrkbacken.
Så småningom blev Gamlakarleby en betydelsefull sjöfarts- och skeppsbyggnadsort. Skeppsvarv fanns bl.a. vid Kaustarviken, Mustakari och Soldatskär. Till en början seglade man endast till Åbo och Stockholm eftersom Gamlakarleby inte hade tillstånd att bedriva utrikeshandel.
1765 fick staden stapelrättigheter, dvs. rätt till fri utrikeshandel, främst tack vare den aktiva kyrkoherden och politikern Anders Chydenius. Gamlakarlebys välstånd ökade snabbt i början av 1800-talet med anledning av tjärhandeln och rederiverksamheten. Stadens borgare köpte tjära av bönderna och fraktade den utomlands, ofta till hamnarna i Medelhavet och England.
Gamlakarlebys handelsflotta var tidvis den största i Finland. Stadens kända skeppsredarnamn var bl.a. Roos, Donner, Rahm och Kyntzell. Den snabba ekonomiska utvecklingen stannade i mitten av 1800-talet, men ett uppsving kom igen i slutet av århundradet i och med industrialiseringen. Gamlakarleby utvecklades till en viktig industristad främst tack vare skinn- och metallindustri.