It is generally assumed, based on graphic data (including misspellings), that palatalization in Latin was operational as early as the second century AD (e.g. Maiden 1995, Repetti 2016, Weiss 2009/2011, among many, many others). Clackson and Horrocks 2007/2011 add that it became general by the fifth century AD (p. 274).
Of course, it didn't happen overnight, neither did it affect all the Latin L1 (native) speakers simultaneously.
Graphic evidence (inscriptions and manuscript spellings):
OZE ‘hodie’ (late second century AD, Algeria)
AZVTORIBVS 'adiutoribus' (CIL VIII 18224, Algeria) Loporcaro 2011: 145
ZODORVS 'Diodorus'(CIL XIV 2325)
ADZVTOR 'adiutor' (CIL VIII, 26683)
ζie 'die' (second century AD, Algeria)
IOSIMVS 'Zosimus' (hypercorrection, Pompeii, CIL IV suppl. I 4599) Loporcaro 2011: 145
iosum, iusum (CL deorsum) (Stotz 1996, v.3, §194.4)
iurnus (CL diurnus) (Stotz 1996, v.3, §194.4)
cf. Weiss "examples from Italy are somewhat later" (p. 513, footnote 57); see Leumann 1977: 130 for more examples.
Evidence from grammarians etc.
Pompeius (GL 5.286 12-14, quoted as in Tronskii 1960, §289):
"quotiescumque ... post ti vel di syllabam sequitur vocalis, illud ti vel di in sibilum vertendum est."
Adams 2007 mentions two types of evidence that might seem at first contradictory, Consentius (possible of the fifth century) "ecce ut Itali ita pingue nescio quid sonant, ut cum dicunt etiam, nihil de media infringant" (as cited in Adams 2007: 203) and Isidore "solent Itali dicere ozie pro hodie." Adams admits that the passage from Consentius can be interpreted differently. He makes a very important observation,
"It is not at all unlikely that there were careful speakers who avoided yodisation and palatalisation in these environments, and that Consentius (himself possibly a Gaul) had heard some of them in Italy, presumably among the educated classes. But it would be hard to believe that these speakers were located only in Italy, or that this was a genuine regional feature" (p. 204).
Weiss adds two more, Serv. ad. Georg. 2.126 and Papirianus (Keil 7.216.8):
See Mras 1948 (in Wiener Studien 63) for a comprehensive account.
It also happened in several stages. For instance, the first stage (syncope, CiV or CeV > CjV) resulted in /j/ (Castellani 1965 argues this process had been finished by the first century AD) - e.g. hodie [ˈɔji] in Sicilian; Weiss mentions some interesting data from Augustine, who has about 100 instances of CjV and only 10 instances of CiV (p. 513, footnote 56).
Weiss adds that "First to undergo palatalization were dentals before yod" (p. 513, footnote 58).
The second stage resulted in either [dʒ] or [dz],cf. Loporcaro 2011, who posits an intermediary stage, [ɟ]; cf. hodie [ˈɔddʒi] in Italian.
cf. Leumann 1977: "Klass. lat. i̯ im Anlaut und Inlaut wird in Vulglat. über eine Spirans j zu einer assibilierten Affrikata dz, etwa i̯ > j > dj > d'j > dz'."
Note: I decided not to use the term Vulgar Latin (ca 250-ca 600 AD, Adamik 2015) in my post after all, following Vincent 2016. Was Vulgar Latin the successor to Classical Latin or were they separate languages? That is a big and extremely difficult question and most likely it is unanswerable.