http://snipurl.com/c8ll, says
Nicol (a unisex vernacular form of
Nicholas) appeared sometime between 1450 and 1650.
Nichole is, interestingly, listed as a variant. (Nicholet is listed as a male pet form of Nicholas--it could to be the forerunner of the feminine
Nicolette.)
http://snipurl.com/c8ln gives more specific dates. Note that Nicholaa / Nicolaa was probably just a Latinisation, used only on documents. In fact, I wonder if
Nicola itself is a Latinisation here, the vernacular form being, again,
Nicol.
Though both of these sites are for English (as in England) usage, it wouldn't be unreasonable to suggest that
Nicole could've been used that far back in
France.
And indeed,
Edgar's Name Pages (
http://snipurl.com/c8lr) says that while
Nicol was only "occasionally" used in England,
Nicole and
Nicola were "fairly popular" in
France and Italy respectively. It's a worded a bit badly, but I'm under the assumption that ENP's meant that
Nicole /
Nicola were used at the same time as
Nicol was being used in England: the Middle Ages.
So it seems that
Nicole's probably been in use since perhaps the 1400s, but only became
really popular in the 20th century.
Miranda (who likes Nicolet, Nicolin, and
Nicol /
Nichol for a boy now)