In the olden days, when one was looking for an email client, you either ended up with Outlook Express (as it was included with Windows) or Outlook, as it was included in pretty much all Office versions.
Back in those days, pretty much all email you received in your client would be transferred via POP, or the Post Office Protocol. As user mailboxes were not that big at the time, I believe it was 20MB at most ISPs in the Netherlands, POP would download your mail into your client and then delete it from the server.
When the first free email providers started, Hotmail (which apparently started with only 2MB) and Yahoo! Mail, you started to get the ability to save more and more mails in your mailbox, but occasionally, you would still have to delete items to free up space. It must be mentioned, that emails back then were also a lot smaller than the ones we have now.
When Gmail was first launched, in 2004, it provided users with a whopping 1GB of mail. Hotmail and Yahoo followed suit and also started offering more storage space.