Wolfenstein was not full 3D.

Not really 3d, the map/engine didn't support a room above another room.

This was also true for doom games, and I think hexen.

Quake was fully 3d.

Duke Nukem had some 2.5 D stuff going on that was more powerful than what doom was doing, but just barely. I think the first fully 3d game that meets your definition is probably 'Descent'