Kisha e Shën Nikollës (Shën Kolli) ndodhet pranë asaj të Shën Mari Vllahernës dhe ka të bashkëngjitura pjesë paraklisesh të rrënuara. Monumenti u ndërtua në mes të viteve 1521 dhe 1565. Mbishkrimi në portën veriore të kësaj kapele mban datën e pikturimit 1591. Mendohet se faza më e hershme e kishës së Shën Kollit mund t’u takojë shekujve XI – XIII.
Sipas Skënder Mihalçkës dhe studimeve të kryera nga Mustafa Arapi mbi piktorët e shek. XVI – XVII, piktura murale e kishës është realizuar nga Onufër Qiprioti. Në brendësi të kishës gjenden dy elementë arkitektonikë (një kolonë dyfishe dhe një kapitel përdorur për tryezën e altarit), të cilët duhet të kenë qenë pjesë e formulimit arkitektonik të kishave paleokristiane të zhdukura në lagjen Kala.