Ankstyvosios krikščionybės laikais (I mūsų eros amžiuje) Pafose buvo pastatyta daug katakombų. Tai požeminės prieglaudos persekiojamiems krikščionims. Šių urvų liekanų, įkastų į žemę, galima rasti visame mieste. Žymiausios iš jų yra Šv.Saliamono katakombos – tai uolų masėje įdubę praėjimai. Jie susilieja, sudarydami požeminę zoną. Istoriškai reikšmingiausias katakombų urvas skirtas šventajam Saliamonui ir septyniems jos sūnums Makabėjams, šventiesiems kankiniams.

Pasak Senojo Testamento, Sirijos karalius Antiochas įvykdė sūnums mirties bausmę už jų tikėjimą, o Saliamonas mirė nuo jų kūnų su malda. Šiame urve buvo palaidoti aštuonių krikščionių kūnai, kurie pagal sūnų skaičių buvo pavadinti „septynių miegamųjų ola“.

IX-XII amžiuje oloje buvo pastatyta bažnyčia, kuri iki šių dienų neišliko. Nuo to laiko ant jo sienų išliko tik freskų pėdsakai. Ant sienų taip pat gausu užrašų, kurių dalį čia paliko kryžiuočiai XIII amžiuje.
Šv. Saliamono oloje kabo piktogramos, ji gerai apšviesta. Jei į katakombas pateksite per vieną iš šoninių praėjimų, galite patekti į gana niūrius siaurus praėjimus. Nusileidę iš Šv. Saliamono olos į žemesnį katakombų lygį, galite rasti senovinį šulinį. Dabar iš jo teka tik plonytė vandens srovelė, tačiau ji laikoma šventa ir, pasak legendos, padeda nuo akių ligų.