Ο Παυλίδης δίδαξε στο Πανεπιστήμιο Πρίνστον, προσληφθείς ως επίκουρος καθηγητής το 1964, και προαχθείς σε αναπληρωτή καθηγητή το 1968 και σε καθηγητή α΄ βαθμίδας το 1975. Το 1980 έγινε μέλος του τεχνικού προσωπικού των Εργαστηρίων AT&T Bell στο Μάρεϊ Χιλ του Νιου Τζέρσεϊ.[7] Το 1982 έγινε αρχισυντάκτης του ερευνητικού περιοδικού IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI)[8] και παρέμεινε σε αυτή τη θέση ως το 1986. Ο Παυλίδης επέστρεψε στη διδασκαλία το 1986 και το 1995 έγινε Διακεκριμένος Καθηγητής, μέχρι τη συνταξιοδότησή του το 2001.[3][6]
Ο Θεοδόσιος Παυλίδης πραγματοποίησε θεμελιώδη έρευνα σε αρκετές περιοχές της αναπτύξεως λογισμικού υπολογιστών, όπως στην αναγνώριση προτύπων (π.χ. αναγνώριση φωνής), την ανάλυση εικόνας, την επιμέλεια εικόνας, την OCR, τη μηχανική όραση και τους ραβδωτούς κώδικες. Συνεισέφερε στο διδιάστατο πρότυπο ISO PDF417 για ραβδωτούς κώδικες, που τους επέτρεψε να έχουν πολύ υψηλή πυκνότητα πληροφοριών και αυτοδιόρθωση λαθών.[6][9] Η εργασία του στη μηχανική (ή υπολογιστική ή τεχνητή) όραση απέφερε έναν αλγόριθμο που μπορεί να διαβάζει ραβδωτούς κώδικες των οποίων μερικές ράβδοι λείπουν.[10][11]
Ο Παυλίδης έχει συγγράψει αρκετά βιβλία και πολλά άρθρα και ερευνητικές εργασίες σε κορυφαία περιοδικά της ειδικότητάς του.[12][13] Επιπλέον, το όνομά του εμφανίζεται σε 15 θεμελιωμένα διπλώματα ευρεσιτεχνίας στις ΗΠΑ.[14]
