Back in the day, I upgraded a Slackware install from kernel 1.3 to 2.0. That was a fucking adventure.
The fun part about back then was that if your machine wouldn't boot or if you couldn't get your modem or pppd working, you probably didn't have another internet connected device so you might have to drive somewhere with a computer...or try to figure it out through books.
Yep. I remember at the time I saw a lot of advice saying "you know you might want to seriously consider just installing your distro from scratch with a newer version." Tracking down all of the dependencies (some of which had to be installed as binaries) was a very manual process.
Edit: Oh and another fun aspect of that time period was that since downloads were so slow on a modem, if you wanted a newer version or to try out another distro, you would go and order a cdrom from a place like Walnut Creek.