Measuring time by lunar cycles began in toward the end of the Paleolithic Age. It allowed them to better time migrations, which made them more efficient hunters.
There are various means by which a lunar calendar could be measured, though the easiest would be from a new moon. A lunar dating system would have only 354.37 days in it, making it an imprecise method. However, it served the purpose of herd predictions.