Etymologically, it does come from "ne-" + "na-" + "vidět", i.e. it was derived from the word to "see". It's probably not a calque from German because the same verb exists in Polish and Russian (as nienawidzić and ненави́деть). But it's been a separate word so long that Czechs don't normally realize there's a connection with "vidět" at all.
In fact, the verb "nenávidět" is defect today, it only exists in its negated form. There is no "návidět" at all. This does create problems for native speakers sometimes when we want to say, for example "I don't hate him." - some people will say "nenenávidím ho", but they realize it's wrong. It's only possible to express this indirectly, such as "Není pravda, že ho nenávidím." (It's not true that I hate him.) or "Nic proti němu nemám." (I have nothing against him.)
EDIT: I just noticed that VladaFu already wrote something similar in his comment 2 years ago.