Τα αρχαιολογικά ευρήματα καταδεικνύουν πως η περιοχή της Κρακοβίας, δίπλα στο όρος Wawel και στην όχθη του ποταμού Βιστούλα, κατοικήθηκε ήδη κατά τη διάρκεια της παλαιολιθικής εποχής. Η πρώτη σλαβική κατοίκηση της περιοχής τοποθετείται τον 6ο μ.Χ. αι. με την παρουσία μιας σλαβικής φυλής στους πρόποδες του Wawel ενώ τον 9ο μ.Χ., όταν ο Μεθόδιος κήρυττε στην περιοχή, λέγεται πως οι κάτοικοι στις όχθες του Βιστούλα ήταν υποτελείς σε έναν μυθικό και πανίσχυρο ηγεμόνα, τον θρυλικό Κράκους, στον οποίο αποδίδεται και η ίδρυση της Κρακοβίας.
Φαίνεται πως οι κάτοικοι της περιοχής ήταν από τους πρώτους σλαβικούς πληθυσμούς που οργανώθηκαν σε μια μορφή κράτους, θέτοντας τα θεμέλια της κατοπινής Πολωνίας.  Ήδη το έτος 966 η Κρακοβία αποτελούσε σπουδαίο εμπορικό κέντρο της ευρύτερης περιοχής της βορειοανατολικής Ευρώπης, όπως μαρτυρούν γραπτές πηγές της εποχής, ενώ η πόλη υπήρξε μάλιστα η πρώτη εστία του Χριστιανισμού στην Πολωνία, καθώς τον 11ο αι. είχε ήδη επίσκοπο.
Το 1038 ο Καζιμίρ Α’ ο Αναστηλωτής διάλεξε την Κρακοβία για έδρα της επικράτειάς του, μετατρέποντάς την στην πρώτη πρωτεύουσα της Πολωνίας, στάτους που διατηρήθηκε έως το 1596, όταν ο Σεγισμούνδος Γ’ Βάσα μετέφερε την πολωνική πρωτεύουσα στη Βαρσοβία.
Από το 1333 έως το 1370 ηγεμόνας της Πολωνίας ήταν ο βασιλιάς Καζιμίρ Γ’ ο Μέγας, ο μεγάλος μεταρρυθμιστής της χώρας. Η βασιλεία του κατέστησε την Κρακοβία σημαντικό εμπορικό, πολιτικό, πολιτιστικό και επιστημονικό κέντρο, με κορύφωση την ίδρυση του πανεπιστημίου της Κρακοβίας το 1364.


Τέλος, την περίοδο 1386-1572 η εξουσία βρισκόταν στα χέρια του οίκου Ζαγκιελόν, του πιο σημαντικού στην ιστορία της Πολωνίας. Ο γάμος μάλιστα της κόρης Λουδοβίκου του Μεγάλου με τον Μεγάλο Δούκα της Λιθουανίας είχε ως αποτέλεσμα τον σχηματισμό της Δημοκρατίας των Δύο Εθνών, Πολωνίας και Λιθουανίας: ο συνασπισμός αυτών των δύο μεγάλων ευρωπαϊκών δυνάμεων της εποχής κυριαρχούσε σε μια τεράστια έκταση από τη Βαλτική έως τον Καύκασο, με την Κρακοβία να αποτελεί το πολιτικό κέντρο αυτής της μεγάλης δύναμης.