Want to undo a step but it is not in undo history
There are several options.

Check in the folder where you have your .blend if there are several files with the same name, but with the extensions .blend1, .blend2 and so on. When you save a .blend, the previous version of the file gets renamed to .blend1, and if there already exists a .blend1, it gets renamed to .blend2. This is a setting in Blender, but if I remember correctly, it's enabled by default. CtrlAltU to open up user preferences, then click File and check the rightmost column to find out whether you have it enabled.

There may also be previous versions of the file lingering in your temporary folder. These could have either the same name as your original file, or they could be named by the process ID of the Blender instance that last had it opened. The temporary folder is usually /tmp on Linux and other Unix like systems. On Windows I'm not 100% certain, but C:\Temp or C:\Windows\Temp may be good places to start searching. On MacOS I have no idea.

You may also try the Decimate modifier, set to Un-Subdivide. On a complex mesh, it probably will not exactly reverse the subsurf, but it might be worth a try.