These people didn't come out of the wilderness, but from Roman-Iron age Germany. They were a powerful tribe which controlled the lower Rhine, (so were the Saxons). This period of Germany is called the Jastorf period and they traded with the Roman Empire and Scythians. Before they were dependable allies of the Roman Empire, they were pirating the coasts of Gaul and Britain along with Frisii and Saxons. They occupied Batavia which was an ideal location for their pirating. It was also adjacent to the most distant, penetrable Roman border. Saxons pushed them from this location into Gaul. Due to their location, they were the first tribe to successfully settle in the late Roman Empire, a trend which others would follow. This was not totally accidental, the best a Germanic ruler could hope for was to enter into the service of the Empire. This began their relationship with the Roman Empire. They were Foederati in Northern Gaul, and by the fall of the Roman Empire, a few were Magister Millitum. They moved to the lower Somme, with their capitol at Tournai, and this became the base of their expansion. It was ideally located, and they continued to have the ocean at their back as they grew. The Battle of Catulian Plains was pivotal for the Salian Franks. I haven't studied it much because of its enigma, but it seems to have determined the pecking order for Western Europe.
They were already a prestigious Germanic people, and to add to this, they were the only Barbarians in Gaul to convert to Catholicism. (A few other Alans may have been.) So they assumed the legacy of the Roman Empire, and then the new Roman faith. They had a string of victories in the name of Catholicism. Dagobert's daughter married Aethelbert of Kent, which initiated the conversion of the Anglo Saxons. Their success was under the Catholic auspices. When it came time to manage their kingdom, Merovingians could not. The church took advantage of this and moved into governance. They don't appear to have had their own realistic goals. They had a job to do, they did it, and that was it. They were great "Magister Militum" and nothing more. Whatever Charlemagne is credited for, he didn't create a lasting kingdom. The question is therefore, why did Catholicism prevail over Arianism? Arianism was the tool of the Byzantine court. It was because of the Huns, Lombards, and other impediments to the Eastern Empire before and after it reconquered Italy. With all these setbacks in the East, the Franks and their new faith could grow.