Vāvela paugurā ir atrastas cilvēka apdzīvotības pēdas jau no akmens laikmeta, tomēr leģenda pilsētas dibināšanu saista ar prinča Kraka vārdu. Krakova pirmoreiz rakstos minēta 966. gadā. Pirmais pilsētu Polijas sastāvā iekļāva Meško I. 1038. gadā Krakova kļuva par Polijas valsts galvaspilsētu. 1241. gadā, iebrūkot mongoļiem, tā tika gandrīz pilnīgi nopostīta. 1259. gadā mongoļi atkal nopostīja pilsētu. Trešais mongoļu uzbrukums notika 1287. gadā, tomēr to, pateicoties jaunajiem aizsardzības mūriem, izdevās atsist.

1364. gadā karalis Kazimirs III nodibināja universitāti. 15. un 16. gadsimtu var uzskatīt par Krakovas "zelta laikmetu" — Krakova ir bagātas un lielas valsts galvaspilsēta. Šeit tapuši daudzi renesanses laikmeta mākslas un literatūras darbi. Kazimežas rajonā uzplauka ebreju kultūra. Pilsētā darbojās daudzi izcili mākslinieki (bieži no Nirnbergas). Tomēr zviedru iebrukumi un mēris samazināja pilsētas iedzīvotāju skaitu un tās nozīmību, līdz karalis Sigismunds III 1596. gadā pārcēla valsts galvaspilsētu uz Varšavu.

Polijas valstij novājinoties, 18. gadsimta beigās tā tika sadalīta starp spēcīgākiem kaimiņiem — Austriju, Prūsiju un Krieviju. Pirmā dalīšana notika 1772. gada 5. augustā, otrā — 1793. gada 23. janvārī. 1794. gadā Krakovā izcēlās Tadeuša Koscjuško vadītā sacelšanās, kas cieta sakāvi. Polijas valsts tika 1795. gada 24. oktobrī pilnībā sadalīta trešoreiz un Krakova nokļuva Austrijas teritorijā Galīcijas un Lodomērijas karalistes sastāvā — tās galvaspilsēta bija Lemberga (mūsdienu Ļvova).

1809. gadā Napoleons izveidoja Varšavas hercogisti, kuras sastāvā iekļāvās arī Krakova. Pēc Napoloena sakāves Vīnes kongress izveidoja Krakovas brīvpilsētu. Tā tika likvidēta un atkal iekļauta Austrijā pēc Krakovas sacelšanās apspiešanas 1846. gadā. 1866. gadā Galīcijai tika piešķrta zināma autonomija un Krakova kļuva par poļu "kultūras Atēnām". Šeit darbojās Jans Matejko, Staņislavs Vispjaņskis un citi poļu kultūras darbinieki.

Sākoties Pirmajam pasaules karam, Juzefs Pilsudskis Krakovā nodibināja poļu karaspēka daļas, likdams pamatus poļu leģioniem. 1918. gadā austrieši nodeva varu poļu varas iestādēm. Starp pasaules kariem Krakova vēl vairāk nostiprināja savu kultūras un izglītības centra statusu. Tika nodibināta tehniskā augstskola un mākslas akadēmija. Pilsēta bija arī ievērojams ebreju kultūras un cionisma centrs. Pēc Vācijas iebrukuma Polijā, Krakova kļuva par Ģenerālgubernatūras centru. To vadīja Hanss Franks, rezidējot Vāvelas pilī. Tika represēti poļu kultūras darbinieki. Ebreji tika ieslodzīti geto, bet vēlāk gandrīz pilnīgi iznīcināti Aušvicas koncentrācijas nometnē. Tajā laikā pilsētā darbojās vācu uzņēmējs Oskars Šindlers.

Sociālistiskās Polijas laikā pilsētas jaunajā Nova Hutas rajonā tika uzcelts milzīgs metalurģiskais kombināts, kas radīja draudus pilsētas ekoloģijai. Līdz ievēlēšanai par pāvestu Krakovā darbojās Karols Vojtila.