Oda's parents were Danish, and he may have been born in East Anglia. His father was said to have been a Dane who came to England in 865, together with the Viking army of Ubba and Ivar, and presumably settled in East Anglia. Oda's nephew Oswald of Worcester later became Archbishop of York. It is possible that Oswald's relatives Oscytel, afterwards Archbishop of York, and Thurcytel, an abbot, were also relatives of Oda, but this is not known for sure.
In Byrhtferth of Ramsey's Life of Saint Oswald, Oda is said to have joined the household of a pious nobleman called Æthelhelm, whom he accompanied to Rome on pilgrimage. While on pilgrimage, Oda healed the nobleman's illness. Other stories, such as those by the 12th-century writer William of Malmesbury, describe Oda as fighting under Edward the Elder and then becoming a priest, but these statements are unlikely. Other statements in the Life have Oda being named "Bishop of Wilton" by the king, who is stated to have been Æthelhelm's brother. The chronicler may be referring, slightly inaccurately, to Aethelhelm cousin of the king. This benefactor has also been associated with bishop Athelm, who reportedly sponsored Oda in his ecclesiastical career. Some sources state that Oda became a monk at Fleury-sur-Loire in France.