Actually, the phrase has nothing to do with the Nazis at all. It is the first line of the first stanza of the German National Anthem. Because of the nationalist connotations, only the third stanza is sung nowadays.

But it should be noted that even the über alles stanza was not originally meant to imply that Germany was superior to other nations. In fact, at the time those lyrics were written, there was no German nation at all. It was meant as a rallying cry for those who wanted one united nation instead of dozens of tiny dukedoms whose rulers were often extremely corrupt and selfish.