352AD- 1st definite date Christmas was celebrated on Dec 25th. It was decided to honour St Nicholas (who came from Myra in what is now Turkey) after his death in 352AD. It was decided by the Roman Bishops so I take it this is where it was first celebrated.
I did have two other answers from the internet - one was 336AD in Rome, the other was 440AD, place not specified. Certainly seems to have been in the 4th century though.