I installed it on an old P1 166 MHz with 64 MB RAM and a hard drive of 2 GB. It was Debian 3.1, in command-line mode. I also used Damn Small Linux on that PC for a few weeks and it behaved very well.
Another successful install was on an AMD K6/2 500 MHz with 64 MB RAM and an 8.4 GB Seagate HDD. Debian 3.1, in both CLI and GUI mode (KDE 3.3.2 if I recall correctly). KDE worked extremely slow, but it worked. When I needed to listen to music I could use XMMS but I preferred command line, with ogg123 and mpg123.
Running Debian in command-line on an old PC is quite fun and you get to learn a *huge* amount of stuff this way.