La primera mención histórica sobre Cracovia proviene de un comerciante, Ibrahim ibn Jakub, que vino de España. El califa de Córdoba lo envió con una misión al emperador alemán, Otto el Grande. Durante esta misión diplomática (960-965) visitó las tierras eslavas y en su relación menciona, entre otros, al príncipe Mieszko, a su guardia personal y la ciudad de Cracovia.
El nombre de la ciudadela cracoviana es tan antiguo que faltan datos históricos que pudieran explicar su procedencia. Lo corroboran las leyendas y cuentos que se han conservado en la memoria del pueblo desde tiempos remotos, transmitidos de generación en generación, narraciones que refieren tiempos tan alejados que hoy día parecen pertenecer a un mundo de fábulas. Gracias a esta herencia del pasado conocemos a los antiguos héroes y los detalles cotidianos de su vida.
Existen dos versiones acerca del origen del nombre de la ciudad. Una de ellas pretende fundarlo en la semejanza con el sonido de la palabra "krakać" (graznar), sonido unido a su vez al cuervo, ave que por aquel entonces era muy popular en las tierras de la actual Małopolska. La leyenda cuenta que en tiempos paganos esta ave de plumas negras gozaba de tal veneración que llegó a ser uno de los dioses locales, protectores.
En las grutas, cuevas y bosques, el pueblo rendía ofrendas de pan a los cuervos, lo que debía garantizar una cosecha grano y abundante, salud y prosperidad. Se creó también una clase específica de sacerdotes encargada no sólo de cuidar de estos pájaros sagrados, sino también realizar secretas ceremonias en su homenaje.
La gente acudía a los sacerdotes para pedirles consejo acerca de las dificultades de la vida y éstos se lo daban, adivinando a partir de las plumas de los cuervos que encontraban en el bosque, y del comportamiento de estas aves, es decir de la manera en la que emitían voces, levantaban el vuelo o se posaban en los árboles. Incluso los príncipes locales aprovechaban de buena gana estos consejos, en particular cuando se preparaban para una expedición de guerra o cuando tenían que tomar algunas decisiones importantes para su reino. De este modo pervivió el culto a los cuervos durante centenares de años hasta el momento en que en tierras polacas comenzó a reinar una nueva religión.
El cristianismo que combatía todos los síntomas de idolatría, también trató como tal el rendir homenaje a las aves. En consecuencia fueron destruidos todos los lugares sagrados conectados con su culto y los sacerdotes fueron dispersados. Pero como el pueblo seguía rindiéndoles culto en secreto, se inició una guerra esta vez contra los mismos pájaros y fueron organizadas despiadadas cazerías contra ellos. Una vez, por orden de un obispo de Cracovia, a los cuervos apresados se les colgó unas piedras al cuello y se los ahogó en las aguas del Vístula. Con el tiempo la memoria de los cuervos sagrados comenzó a desaparecer pero el eco de su nombre permaneció por los siglos fijado en el nombre de la ciudad.
Otra leyenda cuenta que el nombre de la ciudad proviene de un valiente y sabio príncipe llamado Krak o Krakus. Esta versión no contradice a la anterior sobre los cuervos, pues el príncipe, al construir la fortaleza, seguramente pidió la benevolencia de las sagradas aves y, para obtenerla, tomó el nombre de Krak de su graznido ("krakanie" en polaco) y se lo dio también a la ciudad.