Tarinan mukaan Käkisalmi perustettiin siihen, missä kuultiin ensimmäisen kerran käen kukkuvan. Nimen jälkiosa perustuu salmeen, joka on muodostunut tärkeäksi paikaksi kauppareittien risteämässä. Alkujaan paikalla oli karjalainen suurkylä ja siihen liittyvä puinen kylälinnake. Ensimmäinen maininta Vuoksen suuraluetta tarkoittavasta Korelasta on vuodelta 1143. Novgorodilaiset ja myöhemmin venäläiset käyttivät Käkisalmesta Korela-nimitystä 1600-luvulle asti. Käkisalmi sijaitsi Viipurista 85 kilometriä koilliseen Vuoksen rannalla Suomenlahdelta Laatokalle johtavan kauppareitin varrella. Käkisalmi ja Viipuri olivat tärkeitä reitin valvontapisteitä. Käkisalmen sijainti Vuoksen rannalla pari kilometriä ylöspäin siitä paikasta, missä laajan Vuoksen vesistöalueen vesimassat aina Suvannon reitin avaamiseen vuoteetn 1857 asti kokonaisuudessaan purkautuivat Laa­tokkaan, on entisaikaan ollut varsin edullinen. Siksi onkin helposti ymmärrettävissä, että jo varhain muodostui tänne linna ja kauppakeskus. Kun lisäksi näillä kohdin karikoissa kuohuva mahtava Vuoksi oli eri­koisen kalarikas, oli paikkakunnan asukkailla tarjolla kaupan lisäksi toinenkin elinkeino, kalastus ja se lieneekin tuonut ensimmäiset asukkaat nykyisen Käkisalmen paikalle.

Oli tosin ennen muinoin ollut aika, jolloin Vuoksi ei päätynyt Laa­tokkaan, vaan päinvastoin Laatokka purkautui laajana uomana Käkisal­men seudulta Viipurin lahden pohjukkaan. Mutta jääkauden jälkeinen maan kohoaminen ei ollut kaikkialla Suomessa yhtä nopeaa – maa nousi luoteessa enemmän kuin kaakossa – ja niin lopulta Laatokka sai uuden laskuväylän Nevan, joka toi tuon laajan järven vedet Suomenlahden itäisimpään pohjukkaan nykyisen Pietarin luo. Toi­saalta Saimaan vesistön Imatran kautta purkautuvat vedet, jotka var­hemmin olivat päätyneet Viipurin lahteen, kulkivat nyt Käkisalmen kautta Laatokkaan. 1 Vuoksen suunnanmuutoksen yhteydessä oli aliselle Vuokselle myöhemmän Räisälän ja Käkisalmen maalaiskunnan alueelle muodostunut saaririkas järvi, jota venäläisissä kronikoissa esim. v. 1310 kutsutaan Uusijärveksi. Näin olikin Käkisalmi ja sen ympäristö odotta­massa ihmiskätten työtä, joka vähitellen otti tuon seudun viljelykseen. Jo kivikaudella olivat Vuok­sen alajuoksun varret tiheästi asutut, sillä etenkin kalastuksen harjoittamiseean tuo vesirikas seutu oli sovelias. Sen myötä muistoina on löydetty eri puolilya myöhempää Käkisalmen maalaiskuntaa – Näpinlahdelta, Marjalanniemestä, Norsjoelta, Pörtsykästä, Ala- ja Yläpuustista – ja Vuohensalosta sekä myös linnasaarelta erilaisia kivikauden ihmisten työaseita, etenkin talttoja. Kuitenkian vasta pronssikauden jälkeiseltä rautakaudelta on Käkisalmesta ja sen  lähiympäristöstä runsaammin esinelöy­töjä, joskin silloinkin asutuksen painopiste oli myöhempien Räisälän ja Kan­kolan puolella varsinaisen Laatokan rannan jäädessä ilmeisesti sekä elinkeinol­lisista että sotilaallisista syistä jokseenkin asumattomaksi. Käkisalmi mainitaan nimellä Korela ensimmäisen kerran vuonna 1295. Tätä ennen kronikoiden termi Korela viittasi yleisesti karjalaisiin. Paikalle rakennettiin ensin  1200-luvulla, ja alue tuli Novgorodin ruhtinaskunnan alaisuuteen. Käkisalmella syntyi kapina vuonna 1314, jolloin asukkaat kutsuivat ruotsalaiset avuksi Novgorodia vastaan. Ruotsalaiset joukot ajettiin alueelta pois nopeasti ja Käkisalmi pysyi Novgorodin alaisuudessa. Alue pysyi Ruotsin ja Novgorodin välisen kiistan kohteena, kunnes Käkisalmi tuli vuonna 1323 tehdyssä Pähkinäsaaren rauhassa osaksi Novgorodia. Alue läänitettiin liettualaiselle ruhtinas Narimontille, ja hallinnolliseksi keskukseksi tuli Pähkinälinna. Korelan mainitaan 1400-luvulla olevan Novgorodin ruhtinaskunnan toiseksi suurin kaupunki. valtasi Novgorodin kokonaan vuonna 1478, jonka ohessa myös Käkisalmi siirtyi myös Moskovan alaisuuteen.