Yes, a logo is a must in any letterhead. Your logo is a representation and a reflection of your company, just like a letterhead.