Nicolaou ütles, et lahkub ametist poliitilise vastutuse tõttu, kuigi ei olnud juhtumiga isiklikult seotud, vahendab BBC News.
Mõrvadega seoses on vahistatud 35-aastane Küprose armee ohvitser.
Küprose ametiisikuid süüdistatakse aga inimeste kadumise teadete korralikult uurimata jätmises põhjusel, et need inimesed olid sisserändajad.
Küprose president Nicos Anastasiades teatas, et rahuldab Nicolaou tagasiastumisavalduse.
Meeleavaldajad nõudsid varem nii justiitsministri kui ka politseiülema tagasiastumist, süüdistades võimuesindajaid hoolimatuses ja rassismis.
Mõrvatute hulgas olid Filipiinidelt pärit koduabilised Mary Rose Tiburcio, Arian Palanas Lozano ja Maricar Valtez Arquiola. Samuti mõrvati üks Lõuna-Aasia päritolu naine, rumeenlanna Livia Bunea, tema väike tütar Elena ja Tiburcio kuueaastane tütar Sierra.
Mitme naise kadumisest teatati kohe, aga mõrvad said teatavaks alles siis, kui viimase kolme nädala jooksul leiti Tiburcio ja Lozano surnukehad.
Kahtlusalune vahistati Tiburcio internetisõnumeid jälitades. Mees tunnistas hiljem üles mõrvade sarja kolme aasta jooksul ja näitas politseile kätte veel ühe ohvri surnukeha asupaiga.
Võimud otsivad ülejäänud ohvrite surnukehi.
