Z istnieniem twierdzy wiązane jest powstanie Sromowiec i Krościenka. Według Karola Potkańskiego w pobliżu zamku musiała istnieć większa osada, która stanowiłaby dla załogi i przyjezdnych zaplecze gospodarcze. Bronisław Krzan sugeruje, że można identyfikować ją właśnie z Krościenkiem. Średniowieczna osada Crosno, jak pisze M. Książek w swojej pracy Zarys rozwoju przestrzennego Krościenka nad Dunajcem w okresie średniowiecza, miała być pierwotnie położona w pobliżu tzw. Gródka, przy dzisiejszej ul. Pienińskiej, czyli przy drodze prowadzącej do pienińskiej warowni.
mały|Figurka św. Kingi z groty poniżej zamku
Pierwsza uznawana za wiarygodną wzmianka o budowli pochodzi z XIV w. Źródło sugeruje, że po dowodzonym przez Nogaja III najeździe mongolskim na Polskę, Kinga miała się tu schronić wraz ze swoim dworem, kapłanami, rycerzami oraz z 70 klaryskami (wśród których znajdowały się także jej siostry, królewny Jolenta i Konstancja) na początku grudnia 1287 r. Tatarzy nie podjęli wówczas próby zdobycia warowni – usiłowali podpalić zamek przez ostrzał, jednak wycofali się w obliczu nadciągającej z Węgier odsieczy.