Δεν υπάρχουν επαρκείς πληροφορίες για την ιστορία της κυπριακής Αστυνομίας κατά την περίοδο της Φραγκοκρατίας. Γνωρίζουμε ωστόσο ότι υπήρχε αστυνομικό σώμα, πιθανώς οργανωμένο σύμφωνα με τα δυτικά πρότυπα της εποχής. Αρχηγός της Αστυνομίας κατά την περίοδο της δυναστείας των Λουζινιανών ήταν λίζιος ιππότης, διορισμένος από τον βασιλιά, που ονομαζόταν βισκούντης* και ήταν επιφορτισμένος και με άλλα καθήκοντα. Υπό τις διαταγές του βρισκόταν ο μουκτασίπης, υπεύθυνος για την τήρηση και επίβλεψη της τάξης μέσα στην πόλη.
Για την περίοδο πριν από το 1570, μπορεί ν' αναφερθεί η αφήγηση του N. L. Huen που επεσκέφθη την Κύπρο το 1488, και ο οποίος γράφει: Η Κύπρος βρίσκεται σήμερα κάτω από την κυριαρχία των Βενετών που κινδυνεύουν να την χάσουν σύντομα, γιατί οι στρατιώτες και οι χωροφύλακες που έχουν εκεί δεν πληρώνονται και δεν έχουν τα αναγκαία για να ζήσουν ξεφεύγοντας από συνθήκες αθλιότητας...
Μπορούμε να πούμε ότι κατά την περίοδο της βενετικής κυριαρχίας και της Τουρκοκρατίας που ακολούθησε, ο νόμος δεν επιβαλλόταν από καλά οργανωμένη αστυνομική δύναμη, αλλά κυρίως από το στρατό, από ένα είδος στρατιωτικής αστυνομίας και από τους γενιτσάρους.
Όταν η Μεγάλη Βρεττανία κατέλαβε την Κύπρο τον Ιούλιο του 1878, βρήκε ένα αστυνομικό σώμα με δύναμη 275 αξιωματικών, υπαξιωματικών και ανδρών, που είχαν διοικητή αξιωματικό του τουρκικού στρατού με το βαθμό του ταγματάρχη. Οι αστυνομικοί ονομάζονταν ζαπτιέδες και ανάλογες τουρκικές λέξεις υποδήλωναν τους βαθμούχους, όπως λ.χ. ο ζαπίτης (δεκανέας). Η λέξη ζαπτιές προέρχεται από την τουρκική ζάπτ-ετμέκ που σημαίνει συλλαμβάνω. Αυτό και μόνο δείχνει ότι πρωταρχικό καθήκον της Αστυνομίας ήταν τότε η σύλληψη, και οι αστυνομικοί είχαν ως κύριο καθήκον τη συλλογή των φόρων και ως πάρεργο την πρόληψη και εξιχνίαση του εγκλήματος. Η τάξη επιβαλλόταν από το στρατό.
Λίγο μετά την έναρξη της αγγλικής κατοχής η Αστυνομία οργανώθηκε από τους Άγγλους και πήρε το όνομα Κυπριακή Στρατιωτική Αστυνομία. Μέχρι το τέλος του 1879 η νέα Αστυνομία αποτελείτο από 17 αξιωματικούς, 390 ζαπτιέδες και 220 ιππείς. Δημιουργήθηκε επίσης μια δύναμη 400 ανδρών που ονομάστηκαν Κύπριοι Σκαπανείς και επιφορτίστηκαν με βοηθητικά καθήκοντα, όπως εκείνα του φρουρού, του συνοδού, του βαριάνου στις φυλακές, του επόπτη στα χωριά που είχαν επιδημικές αρρώστιες των ζώων κλπ. Επίσης οι Σκαπανείς επιστρατεύονταν και για εργασίες δύσκολες, όταν δεν βρίσκονταν εργάτες γι’ αυτές, όπως η αντιμετώπιση της κατάστασης από τις καταστρεπτικές πλημμύρες στη Λεμεσό το 1880. Στην ουσία η Αστυνομία και το βοηθητικό σώμα των Σκαπανέων είχαν αποστολή σώματος Χωροφυλακής.
Λίγο αργότερα τα δυο σώματα συγχωνεύθηκαν και η δύναμη του νέου σώματος καθορίστηκε σε 8 Άγγλους αξιωματικούς, 9 Κυπρίους αξιωματικούς, 220 ιππείς και 473 ζαπτιέδες. Σύνολο: 710 άντρες. Ο σχετικός νόμος, που έθεσε τα θεμέλια της Αστυνομίας, θεσπίστηκε τον Ιανουάριο του 1879 και προνοούσε μεταξύ άλλων και για τη σύσταση, την αριθμητική δύναμη, τον όρκο, την περίοδο εγγραφής των αστυνομικών, τις εξουσίες, τις απολύσεις, την πειθαρχία, τα επιδόματα κλπ. Ο νόμος αυτός είχε τίτλο: Ο περί αστυνομικής πειθαρχίας Νόμος.
Τον Μάιο του 1879 θεσπίστηκε κι άλλος νόμος που προνοούσε για τη σύσταση στις πόλεις ειρηνοδικείων για την εκδίκαση μη σοβαρών υποθέσεων όπως μέθης, καβγάδων, ανησυχίας, μικροκλοπών κλπ. Στις 27 Δεκεμβρίου του 1879, άλλος νόμος δημοσιεύτηκε, ο οποίος εξουσιοδοτούσε τον ύπατο αρμοστή να διατάσσει την εγγραφή στο αστυνομικό σώμα κατάλληλων ανδρών που ο αριθμός τους να μη υπερβαίνει τους 1.000, και που σαν ένα συμπαγές εξοπλισμένο σώμα θα ενίσχυε την Αστυνομία στην υπηρεσία της αποικιακής κυβέρνησης. Ο αριθμός της επικουρικής αυτής δύναμης αυξομειωνόταν από καιρού εις καιρόν, ύστερα από απόφαση του ύπατου αρμοστή και σύμφωνα με τις καταστάσεις, πολιτικές και άλλες. Τα καθήκοντα της επικουρικής μονάδας, που ήταν ένα είδος χωροφυλακής, ήταν η εξιχνίαση και η πρόληψη του εγκλήματος, η σύλληψη των παρανομούντων, η διατήρηση της ειρήνης και της δημόσιας τάξης και, σε περίπτωση ανάγκης, η συμμετοχή στην άμυνα του νησιού. Μέλη της μονάδας χρησιμοποιούνταν επίσης σε διάφορα έργα, όπως η κατασκευή ή συντήρηση δημοσίων δρόμων και κτιρίων.
Αξίζει να αναφερθεί ότι κατά το 1878 δημιουργήθηκε για πρώτη φορά Δημοτική Αστυνομία στη Λάρνακα, με σκοπό τη διατήρηση της τάξης και άλλα συναφή καθήκοντα μέσα στην πόλη. Το σώμα αυτό συγχωνεύθηκε λίγο αργότερα με εκείνο της Στρατιωτικής Αστυνομίας.
Αργότερα θεωρήθηκε σκόπιμο όπως η Κυπριακή Στρατιωτική Αστυνομία, που δημιουργήθηκε με βάση τον νόμο του Ιανουαρίου 1879, και η Χωροφυλακή, που δημιουργήθηκε με βάση τον νόμο της 27 Δεκεμβρίου 1879, συμπτυχθούν κάτω από μια συμπαγή διοίκηση. Έτσι, με σχετικό νόμο που δημοσιεύτηκε στις 19 Νοεμβρίου του 1880, η συνδυασμένη δύναμη τέθηκε κάτω από τη διοίκηση του αρχιαστυνόμου και ήταν γνωστή σαν Κυπριακή Στρατιωτική Αστυνομία.
Οι αλλαγές που έγιναν κατά την περίοδο μεταξύ του 1880 και του 1900 ήσαν συγκριτικά επουσιώδεις. Μια από τις πιο σημαντικές ήταν η δημιουργία αγροτικών αστυνομικών σταθμών σ' ολόκληρη την Κύπρο (το 1888), για την καταπολέμηση του εγκλήματος που είχε πάρει διαστάσεις ανησυχητικές. Το μέτρο, σύμφωνα με την ετήσια έκθεση του 1888, έδωσε μεγάλη ανακούφιση και ικανοποίηση στον αγροτικό κόσμο και δημιούργησε αίσθημα ασφάλειας στους κατοίκους της υπαίθρου.
Οι όροι υπηρεσίας των μελών της Αστυνομίας την εποχή εκείνη δεν ήταν ικανοποιητικοί. Οι μισθοί ήταν χαμηλοί κι υπολογίζονταν σε μεροκάματα, ενώ δεν υπήρχαν συντάξεις, ούτε και η σιγουριά της μονιμότητας.