First appears in texts from the late Muromachi period as an eastern-dialect term. Sometimes described as related to ancient eastern-dialect negative ending なふ (nafu), but there is a sizable gap of time between the apparent disappearance of nafu and the emergence of nai.
That said, both nafu and nai probably derive ultimately from ancient copula or stative verb ぬ (nu), with the negative sense originating from the 未然形 (mizenkei, “irrealis or incomplete form”) of the verb stem, to which these endings attach.
The nai ending conjugates as a regular -i adjective just like the adjective nai in modern Japanese, but the ending conjugation is originally different from the adjective. In the Edo period, the ending conjugated irregularly, including nanda instead of modern nakatta (past), and naikereba instead of modern nakereba (conditional).