(I had tailpipe emissions tests in Virgina in the early 90's)
Tailpipe testing started in the Northern Virginia area (to date, the only part of Virginia that requires emissions testing) around 1985 or so. There's some archived Washington Post articles about it, at the time that it started. They listed all of the testing stations (which were and are in repair shops and dealerships--Virginia never ran their own testing facilities).
About the same time that it started in the Chicago area, perhaps not coincidentally. I remember going with my mom when she went to get the car tested for the first time. In Illinois, the testing facilities are run / owned by the state.