Dune II was definitely influenced by Herzog Zwei, but not everyone had a Genesis, and I don't think Herzog Zwei really had a concept of base management or resource gathering, which have obviously become integral to the RTS games today.
I absolutely loved that game, though!
I don't really recall it having any story, though.