When the legions, under the leadership of Guisureth Hratgason, a popular and successful leader, 'defect' to the German tribes across the border (circa 312 - 320) after Constantine declares for Christianity. Joining the Goths in the East, they are faced with some jockying for power between the gothic King (I forget his name, but I think it is Eormanric), and several competitors. In OTL the competition contributed to the breakup of the Goths into east and west. but in this, the newly arrived legions support the king, stabilizing the kingdom.
In exchange for hte support, the king names Guisureth to be a member of the his tribe, adopting him directly into his family. This puts Guisureth in line for the 'throne'.
Although the Goths were at this time extremely warlike (so much so that the translater of the bible into Gothic would translate the battle scenes on the grounds that they didn't need encouragement), Guisureth's success in battle begins to attract followers to the religion from among the tribesmen. It is at this point that the Mithras begins to take on attributes of Thor, a highly popular german god.
The two important changes that come with the legions are: 1) medical techniques which were (for that time and place) very advanced, and 2) improved discipline of the Mithraic tribal warriors. In addition, Wulfingas (?) the Christian missionary arrives and translates the bible in to Gothic. This act begins to attract some adherents, but also provokes a sort of mini-counter literacy among the followers of Mithra, and the basic tenets of the faith are written down. Christians are soon surpressed, but the literacy they brought continues to grow. It is at this time that the Mithraic 'Fathers' become literate.
As a result, when the Huns begin to filter into Europe in and around 320 A.D. there are actually some pretty good troops there to resist them. The goths defeat the Huns in a series of stunning victories, despite some overwhelming odds.
One aspect of this defeat of the Huns are several tales of incredible strength and bravery that the 'skalds / scops' turn into epic length poems and take to the rest of the Northern peoples. Central to these poems is the concept that Mithra brings success in battle.
Soon even the most distant heathen has heard of Mithra, and many send messnagers to ask about the religion.