It seems that the history of negatives in English (and some other Indo-European languages too) is apparently somewhat complicated. The original simple negative in English was ne, and it was used from Old English to late Middle or early Modern English. This negative particle was also prefixed to form other negatives, like none and never.
The word no is apparently one of these prefixed forms. It's ne + o (an obsolete word meaning 'ever'), presumably originally meaning 'never', but in Old English it apparently was used as a more emphatic 'no', along the lines of 'not at all' or 'no way'. Interestingly, nay comes from the Old Norse cognate of no.
Not comes from a reduced form of nought/naught, which was also used in the emphatic-but-generic 'no' sense.
As to why they exist in this particular distribution today, I'm not sure, but a somewhat similar situation exists in French. The closest equivalent to no is non, and the closest to not is ne . . . pas, which goes around verbs. But to say "why not?" you say "pourquoi pas?" Pas originally meant 'step' (and is related to pace), and it was added to negative expressions with ne for emphasis, meaning literally 'not a step'. But eventually the emphasis was lost, and it became the generic negative, much like no and not in English. I'm guessing that the Spanish no and French non are also formed from ne (which existed in Latin too) plus some other root.
Unfortunately, I don't know enough about negatives cross-linguistically to say whether it's common to have multiple generic negatives that are used in different situations. But I wouldn't be at all surprised if Hebrew and Spanish are unusual in having only one form.
