While the earliest evidence in texts written in the Latin alphabet for the sound change of Latin [w] to [β] or [v] (which can be referred to with the linguistic term "fortition", i.e. "strengthening") may date to the first century AD (as discussed in Nathaniel's answer), evidence in the form of Greek-alphabet transcriptions of Latin V with the Greek letter β (instead of the digraph ου) seems to show up considerably earlier.