Bei den Kongresswahlen des Jahres 1984 wurde er im fünften Wahlbezirk von Michigan in das US-Repräsentantenhaus in Washington, D.C. gewählt, wo er am 3. Januar 1985 die Nachfolge von Harold S. Sawyer antrat. Nach vier Wiederwahlen konnte er bis zu seinem Tod im Kongress verbleiben. Seit dem 3. Januar 1993 vertrat er dort als Nachfolger von Howard Wolpe den dritten Distrikt seines Staates. Während seiner Zeit im US-Repräsentantenhaus wurde dort im Jahr 1992 der 27. Verfassungszusatz verabschiedet.
Kurz vor den Wahlen des Jahres 1992, die er erneut für sich entschied, wurde bei Henry ein Gehirntumor festgestellt. Er unterzog sich einer entsprechenden Behandlung und konnte am 3. Januar 1993 den Eid für eine neue Legislaturperiode im Kongress ablegen. Danach verschlechterte sich sein Gesundheitszustand. Am 31. Juli 1993 erlag Paul Henry in Grand Rapids seiner Krankheit.