بفضل البيئة الطبيعية المواتية للمدينة، استوطن سكان ستولاك ومنطقتها منذ العصور القديمة. جذبت أراضي الصيد الغنية، إلى جانب ثرواتها الطبيعية الأخرى، إنسان ما قبل التاريخ، ثم الإليريون والرومان والسلاف، الذين تركوا وراءهم ثروة من الأدلة الأنثروبولوجية. استُوطنت المنطقة منذ ما لا يقل عن ١٥,٠٠٠ عام، كما يتضح من العلامات الموجودة في كهف بادانج، والتي أرجعها الخبراء إلى ما بين ١٢,٠٠٠ و١٦,٠٠٠ قبل الميلاد. على بُعد ثلاثة كيلومترات غرب ستولاك، تقع مقبرة ستيكاك الرائعة التي يعود تاريخها إلى القرنين الخامس عشر والسادس عشر: راديمليا. نُحتت على شواهد قبور ستيكاك هذه نقوشٌ تذكارية، وصورٌ مفصلة للمتوفى، وزخارف مثل كروم العنب، ومشاهد الصيد، والحيوانات البرية. يُعتقد أن خمسة من شواهد قبور راديمليا تُشير إلى قبور أفراد من عائلة هرابرين ميلورادوفيتش فالاشيان. علي باشا رضوان بيجوفيتش (١٧٨٣–١٨٥١)، الحاكم شبه المستقل (الوزير) للهرسك العثمانية من ١٨٣٣ إلى ١٨٥١، ولد في حي بيجوفينا في ستولاك.