Best regards seems to be quite a popular valediction used in business emails, along with variants kind regards, or just regards.
The spoken expression "give him my regards" would appear to be a suitable starting point for the written valediction Regards, but when did this become best regards? Has it ever existed in written letters?