Oblasti, kde se dnes nacházejí skalní města, byly zaplaveny mořem. Mluvíme o období svrchní křídy. Když moře po 12. milionech let ustoupilo, zbyla zde ohromná tzv. pískovcová tabule (uložené mořské sedimenty), která byla koncem druhohor narušena tektonickou činností. Začátkem třetihor (před více než 200 mil. let). V té době došlo k rozlámání pískovcové tabule a do vzniklých puklin proniklo magma, které vytvořilo povrchové sopečné výlevy. Působením další sopečné činnosti, povětrnostních vlivů a eroze, došlo k rozšiřování puklin a tak vznikaly soutěsky a rokle a zároveň se části ker rozpadaly v jednotlivé skalní věže. Proces zvětrávání a eroze působí na skály dodnes.
Kdysi bylo skalní město jedním velkým pralesem, kam lidská noha nevkročila. Celý komplex hraničních hor včetně Krkonoš i Orlických hor byl od dob Římanů nazýván Hercynským lesem, který byl tak hustý, že v něm skály nebyly vidět. Počátky kolonizace sahají až do 13. století. V té době hluboké lesy a neprostupné hvozdy vytvářely přirozenou ochranu před vpádem cizích vojsk na naše území. Později sloužili skalní oblasti jako útočiště pro místní obyvatele, kteří se do nich chodili schovávat. První zmínky o pískovcových skalách pocházejí z oblasti Broumovských stěn. Na tuto oblast narazil člověk už v pravěku. Výstižný název Stěny je poprvé doložen roku 1213 a 1229 v břevnovských klášterních listinách. V této době se kolonizace dotkla i Adršpašsko-teplických skal a to podél toku řeky Metuje a Olšovky.
Ve 13. století vznikly na řece Metuji Teplice a v oblasti skal dva hrady. V Teplických skalách hrad Střmen (používal se i název Střemen) a cca 2 km od Adršpachu hrad Adršpach. Další hrad v Jiráskových skalách s názvem Skály, vznikl až o něco později. Zřícenina hradu Střmen je součástí prohlídkového okruhu v Teplických skalách v podobě vyhlídkového místa.
Hrad Střmen je uveden v Majestas Carolina Karla IV. Kolem roku 1363 byl majetkem Hynka z Dubé a z Náchoda. Pozdější historie hradu není zcela známá, ale pravděpodobně byl ve 14. století během husitských válek zbořen. V současné době se v místech, kde kdysi hrad stával nacházejí jen nepatrné pozůstatky původních staveb a krásná vyhlídka do okolí, ke které se dostanete po strmém, dlouhém schodišti. Od roku 1964 je původní stavba chráněna jako kulturní památka.
