Wolfenstein 3D came out in 1992
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'