Paul Koettig wurde am 14. September 1856 in Dresden als Sohn des Bergrates Koettig geboren. Er besuchte die Böhmische Realschule, danach die Kreuzschule Dresden und die Universität Leipzig. Nach bestandenem Examen wurde er 1883 als Referendar beim Polizeipräsidium Dresden angestellt und später mit verschiedenen polizeiliche Aufgaben betraut. Er war, bevor er Polizeipräsident von Dresden wurde, Vorstand der Dresdner Kriminalpolizei. Insofern war er mit allen Einzelheiten, Bedürfnissen, Mängeln und Ausgestaltungsmöglichkeiten des kriminalpolizeilichen Dienstes vertraut. Schon als Chef der Dresdner Kriminalabteilung war er ein Schrittmacher der Anthropometrie in Deutschland. Unmittelbar vor seiner Ernennung zum Polizeipräsidenten führte er das Fingerabdruckverfahren in Dresden ein. Er organisierte einen Identifizierungsdienst für das gesamte sächsische Staatsgebiet und schuf damit die erste technisch einwandfrei funktionierende daktyloskopische Landeszentrale in Deutschland. Der nach seinen Direktiven ausgestaltete Dresdner Erkennungsdienst wurde zum Vorbild für Einrichtungen dieser Art in anderen Bundesstaaten.