An almanac made at Rome in 354 for a Christian named Valentinus carries, among the days of the martyrs, one line that is not a martyr: VIII kal. Ian. natus Christus in Betleem Iudeae — the eighth day before the kalends of January, Christ born in Bethlehem of Judaea. That is 25 December, and it is the earliest dated evidence anyone has that the day was kept. Everything earlier is inference. The list it sits in was probably drawn up in 336, which pushes the practice back a further generation but no further, and the East kept 6 January for the same feast until the late fourth century, when the two calendars converged from both directions rather than one adopting the other. The document does not say why the day was chosen, and the two standing explanations - a computation from 25 March, and a Christian answer to the sun's birthday kept at Rome on the same date - are both later reasoning about an earlier fact. What the Chronograph establishes is narrower and firmer than either: by 354 at Rome, the day was 25 December and it was written down.
Chronograph of 354 (the Calendar of Filocalus) · Depositio Martyrum (part 12), the entry at VIII kal. Ian.