Gildas adds several small details that suggest either he or his source received at least part of the story from the Anglo-Saxons. The first is when he describes the size of the initial party of Saxons, he states that they came in three cyulis (or "keels"), "as they call ships of war". This may be the earliest recovered word of English.
Europrogocontestovision has some interesting theories on what this word might really mean.
But of course defining the beginning of English from the moment the Anglo-Saxons arrived is arbitrary. The language they spoke when they began their channel crossing was the same language they spoke when they arrived on the island. And I wonder, if we still called Old English Anglo-Saxon, would we think the same about this word?
We do have records of English from before the invasion, altho we call it "Proto-Germanic". Finnish preserves forms in loanwords, for instance kuningas "king", borrowed from Proto-Germanic *kuninǥaz.