Does a language exist whose older forms are known to have lacked the category of grammatical gender, and which proceeded to evolve one (perhaps from a non-gender-based system of noun classes)? Are "pre-gender" stages of language evolution, where they existed, universally a thing of such distant past as to be beyond reconstruction?
Surprisingly, Indo-European seems to be an example. Silvia Luraghi has an article "The origin of the Proto-Indo-European gender system: Typological considerations" (Folia Linguistica 45/2 (2011), 435–464) which discusses this, and it appears that there is agreement that the M/F/N system of later languages developed from a two-gender system where masculine and feminine were not distinguished, and the system was based on an animate / inanimate.
Khasi, an Austroasiatic language spoken in Northeast India, differs from practically all other members of that family (at least those outside the Munda branch, as @user6726 rightly points out) in having grammatical gender. There is a paper about this: Lili Rabel-Heymann, ‘Gender in Khasi Nouns’, Mon-Khmer Studies Journal IV: 247-72 (1977), available online here.
Every Khasi noun is preceded by a gender indicator commonly known as an “article,” a term borrowed for reasons of convenience from the grammar of Indo-European. This gender indicator is repeated before the verb, and is then known as a pronominal verbal prefix. A morpheme identical with the nominal article and the verbal pronominal prefix functions in free form as a personal pronoun. It might therefore be said that the Khasi pronoun occurs as a free morpheme by itself and as a bound form before nouns and verbs. In any case, the prenominal and preverbal forms always agree with respect to number and gender. (Heymann p. 247)
While as far as I know there are no surviving records of earlier versions of the language that did not exhibit this feature, we can infer that what was originally a pronoun came to do double duty as a gender marker. And the reason for the innovation – contact with Indo-Aryan languages in the region – can also be inferred.