스털링성이 자리잡은 이른바 캐슬힐 (Castle Hill)은 본래 스털링 실 (Stirling Sill)이라는 지질구조의 일부로서, 지금으로부터 약 3억 5000만년 전 형성된 석영휘록암 (quartz-dolerite)이 빙기 활동으로 큼직한 바위로 깎여 만들어졌다.[1] 캐슬힐 바로 동쪽면의 고원힐 (Gowan Hill)에는 힐포트 유적이 위치해 있어, 일찍부터 이곳 지형을 활용하게 된 것으로 보인다.[2]

로마 제국이 브리튼섬을 점령하던 시기 로마인들은 스털링 일대에는 관심을 두지 않고 둔 (Doune) 지역에 요새를 세웠다. 다만 동시기 캐슬힐 일대는 매아태족 (Maeatae)이 점령했을 것으로 추정된다.[3] 이후 마노 고도딘 (Manaw Gododdin)의 요새가 자리했을 것으로 보이며, 7세기~8세기에 이르러 유데우 (Iudeu)라는 촌락이 있었다는 기록이 획인된다. 유데우는 서기 655년 머시아 국왕 펜다가 베르니시아의 오스위그를 상대로 포위전에 나선 무대이기도 하다.[3] 그로부터 30년 뒤에는 더닉테인 전투 (Battle of Dun Nechtain)에서 노섬브리아인들이 패배하면서 픽트인의 영토로 넘어갔다. 하지만 캐슬힐에서 진행된 발굴조사 결과로는 중세 후기 이전에 이 언덕 일대를 점령한 흔적은 발견되지 않았다.[4]

한편 스털링과 관련된 몇가지 전승이 전해져 내려오는데 여기서는 '스노둔' (Snowdoun)이란 이름으로 소개된다.[5] 16세기 영국의 역사학자 헥터 보스 (Hector Boece)는 저서 <스코틀랜드의 역사> (Historia Gentis Scotorum)에서 스털링에 요새를 세운 것은 로마인들이며 아그리콜라가 주도했다고 소개한다.[6] 그리고 스코틀랜드의 초대 국왕으로 전해져 내려오는 케네스 맥알핀이 9세기경 픽트인 왕국을 점령하면서 스털링에 있는 성을 포위했다고 적고 있다.[7] 하지만 학계에서 보스는 기록의 신빙성이 떨어져 믿기 어려운 역사학자로 여겨지고 있다.[6]

연대기 작가 윌리엄 우스터 (William Worcester)는 스털링에 영국의 전설적인 아서왕의 궁궐이 있었다고 주장하는가 하면, 이곳에 성 모데나가 예배당을 세운 것이 오늘날 스털링성의 유래라는 전승도 있다. 성 모데나는 에든버러성도 똑같이 단초를 제공했다고 알려진 전설 속의 성인으로[8] 현재는 모드웨나 (Modwenna)나 모닌 (Monnine) 등의 초창기 기독교 성인들의 활동이 모데나 성인이란 가공의 인물로 만들어졌다는 것 정설이다.[9]

스털링성이 문헌에 처음으로 기록된 것은 1110년경으로, 스코틀랜드의 알락산다르 1세가 이곳에 예배당을 세워 바쳤다는 기록이 확인된다.[10] 알릭산다르 1세는 이후 1124년에 스털링 예배당에서 숨을 거뒀기 때문에, 당시 스코틀랜드 왕실의 거점으로 삼으려 했던 것으로 보인다. 알락산다르 1세의 뒤를 이어 즉위한 데이비드 1세 치세에 이르러 스털링시는 칙허자치도시 (royal Burgh)가 되었으며, 스털링성은 행정의 중심지로 거듭났다.[11] 윌리엄 1세는 스털링성 남서쪽에 사슴 사냥터를 세웠으나, 1174년 잉글랜드군에게 인질로 잡힌 이래 팔레즈 조약에 의거하여 스코틀랜드의 여러 성을 포기해야 했는데, 에든버러성과 더불어 스털링성도 그 중 하나였다. 다만 잉글랜드가 실제로 스털링성을 점거했다는 증거는 확인되지 않고 있으며, 1189년 잉글랜드의 리처드 1세가 스털링성을 공식 반환하면서, 스털링성은 스코틀랜드 왕실에서 아끼는 대표 왕궁으로 돌아갔다. 윌리엄 1세는 1214년 스털링성에서 사망했으며[12] 1260년대에는 알락산다르 3세가 사슴 사냥용으로 뉴파크 (New Park)를 구획하였다.[13]

1286년 알락산다르 3세가 서거하자 스코틀랜드 국왕 자리를 두고 승계 분쟁이 벌어졌고, 잉글랜드 국왕 에드워드 1세는 왕위 경쟁의 중재자로 나서기 시작했다. 1291년 스코틀랜드로 북진한 에드워드 1세는 중재 기간 동안 스털링성을 비롯한 여러 왕궁은 본인이 관리하겠다며 내놓을 것을 주장하였다. 이후 에드워드 1세는 존 발리올이 왕위를 승계해야 한다는 결론을 내렸는데, 여기에는 존 발리올을 자신의 꼭두각시 국왕으로 삼으리란 계산이 작용하였으나, 정작 존 본인은 에드워드 1세의 요구에 굴복하지 않겠다는 뜻을 내비쳤다.[14]

결국 1296년 에드워드 1세가 스코틀랜드를 침공하면서 스코틀랜드 독립 전쟁이 60여년간 이어지는 결과를 낳았다. 전쟁 극초기에는 스코틀랜드군의 후퇴로 스털링성이 버려지면서 잉글랜드군이 들어와 점거하였다.[15] 이듬해에는 스털링교 전투에서 앤드류 모레이와 윌리엄 월리스가 이끄는 스코틀랜드군이 승리하여 잉글랜드군이 퇴각하고 다시 스코틀랜드군이 점령하였다. 전투 과정에서 수비군 다수가 전사하였고, 잉글랜드측 지휘관이었던 윌리엄 피츠워린과 마머듀크 트웽 (Marmaduke Thweng)이 스털링성으로 후퇴하였으나 스코틀랜드군이 성을 포위하면서 머지않아 굶주림을 이기지 못하고 항복했던 것이었다.[16] 그러나 그 다음 여름에 폴커크 전투에서 잉글랜드군이 승리하면서 스코틀랜드군이 스털링성을 버리고 떠나면서 다시 주인이 바뀌었다. 에드워드 1세는 스털링성의 수비 강화에 나섰으나 1299년 로버트 브루스가 이끄는 군대에 포위되었고 에드워드 1세는 수비군 구출에 실패하면서 항복하고 말았다.[17]