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.
Jo keskiajalla Kokkolassa oli satama, laivanrakennuspaikka ja kauppapaikka. Maankohoaminen on ollut keskeinen tekijä Kokkolan historiassa. Se on muokannut ympäristöä merkittävästi ja vaikuttanut mm. satamalaitoksen ja kaupankäynnin kehittymiseen. Kauppaa harjoitettiin pohjanlahden rannikkoa pitkin ja maanviljelys, metsästys, kalastus ja hylkeenpyynti olivat myös tärkeitä elinkeinoja.
Kokkolan historiassa hyvin tärkeäksi muodostunut tervanvienti aloitettiin jo 1500-luvulla. Tuolloin käytiin myös Pohjoismaiden viimeinen merkittävä talonpoikaiskapina, nuijasota, jonka tapahtumat liittyvät läheisesti myös Kokkolaan.
Vuonna 1620 syyskuun 7. päivänä Ruotsin kuningas Kustaa II Adolf allekirjoitti asiakirjan, jolla pienestä Ristirannan maanviljelys- ja kalastajakylästä tuli kaupunki nimellä Gamlakarleby. Kokkola vakiintui kaupungin suomenkieliseksi nimeksi myöhemmin. Nykyinen kaupunginsalmi oli kaupungin perustamisen aikoihin kapea merenlahti, joka ulottui Kirkonmäelle saakka.
Pikkuhiljaa Kokkolasta kehittyi merkittävä merenkulku- ja laivanrakennuspaikka. Laivanveistämöitä oli mm. Kaustarinlahdella, Mustakarilla ja Soldatskärissä. Aluksi purjehdittiin vain Turkuun ja Tukholmaan, koska Kokkola ei saanut ns. maakaupunkina harjoittaa ulkomaankauppaa.
Vuonna 1765 kaupunki sai tapulioikeudet eli oikeuden vapaaseen ulkomaankauppaan lähinnä aktiivisen kirkkoherran ja valtiopäivämiehen Anders Chydeniuksen ansiosta. Kokkola vaurastui nopeasti 1800-luvun alussa juuri tervakaupan ja laivanvarustuksen ansiosta. Kaupungin porvarit ostivat tervaa talonpojilta ja veivät ulkomaille, usein Välimeren ja Englannin satamiin.
Kokkolan kauppalaivasto oli ajoittain Suomen suurin. Kaupungin tunnettuja laivanvarustajanimiä olivat mm. Roos, Donner, Rahm ja Kyntzell. Nopea taloudellinen kehitys pysähtyi 1800-luvun puolivälissä, mutta nousi taas uudelleen vuosisadan loppupuolella teollistumisen myötä. Kokkolasta kehittyi tärkeä teollisuuskaupunki varsinkin nahka- ja metalliteollisuuden ansiosta.