Του ΤΑΠΜ προΐσταται Διευθυντής. Το Τμήμα χωρίζεται σε δύο Τομείς: τον Τομέα Αρχείου Πληθυσμού και τον Τομέα Μετανάστευσης. Ο κάθε Τομέας χωρίζεται σε επιμέρους Κλάδους, κάθε ένας εκ των οποίων είναι υπεύθυνος για μέρος των αρμοδιοτήτων του Τομέα. Του κάθε Κλάδου προΐσταται ένας Διοικητικός Λειτουργός. Επίσης, κάθε Κλάδος στελεχώνεται από γενικό γραμματειακό προσωπικό. Οι εργασίες των Τομέων υποστηρίζονται από το Αρχείο, το Λογιστήριο και τη Μονάδα Εκτύπωσης Εγγράφων.
Η εξυπηρέτηση του κοινού διεξάγεται στα Κεντρικά Γραφεία του Τμήματος, στα Κέντρα Εξυπηρέτησης του Πολίτη (Τμήμα Δημόσιας Διοίκησης και Προσωπικού, Υπουργείο Οικονομικών), στις Επαρχιακές Διοικήσεις (Υπουργείο Εσωτερικών) και στα Επαρχιακά Κλιμάκια της Υπηρεσίας Αλλοδαπών και Μετανάστευσης της Αστυνομίας Κύπρου. Τα τελευταία στελεχώνονται μερικώς από προσωπικό του Τμήματος.
Επιπρόσθετα, το προσωπικό του Τμήματος στελεχώνει μερικώς τρία από τα οδοφράγματα.
