He has often been called "the last of the Romans". Edward Gibbon refers to him as "the man universally celebrated as the terror of Barbarians and the support of the Republic" for his alleged victory at the Catalaunian Plains.
Aetius was born at Durostorum in Moesia Inferior (modern Silistra, Bulgaria), around 391. His father, Flavius Gaudentius, was a Roman general of Scythian origin, As the term "Scythian" was frequently used in late antiquity for East Germanic tribes, Joseph Cummins notes that Gaudentius was possibly of Gothic origin. Aetius' mother, whose name is unknown, was a wealthy aristocratic woman of Italian ancestry. Before 425 Aetius married the daughter of Carpilio, who gave him a son, also named Carpilio. Later he married Pelagia, widow of Bonifacius, from whom he had a son, Gaudentius. It is possible that he had also a daughter, wife of Thraustila who avenged Aetius' death by killing emperor Valentinian III.
As a boy, Aetius was at the service of the imperial court, enrolled in the military unit of the Protectores Domestici and then elevated to the position of tribunus praetorianus partis militaris, setting him up for future political eligibility. Between 405 and 408 he was kept as hostage at the court of Alaric I, king of the Visigoths. In 408 Alaric asked to keep Aetius as a hostage, but was refused, as Aetius was sent to the court of Uldin, king of the Huns, where he would stay with the Huns throughout much of the reign of Charaton, Uldin's successor. According to some early historians, Aetius's upbringing amongst militaristic peoples gave him a martial vigour not common in Roman generals of the time.
In 423 the Western Emperor Honorius died. The most influential man in the West, Castinus, chose as his successor Joannes, a high-ranking officer. Joannes was not part of the Theodosian dynasty and he did not receive the recognition of the eastern court. The Eastern Emperor Theodosius II organized a military expedition westward, led by Ardaburius and his son Aspar, to put his cousin, the young Valentinian III (who was a nephew of Honorius), on the western throne. Aetius entered the service of the usurper as cura palatii and was sent by Joannes to ask the Huns for assistance. Joannes lacked a strong army and fortified himself in his capital, Ravenna, where he was killed in the summer of 425. Shortly afterwards, Aetius returned to Italy with a large force of Huns to find that power in the west was now in the hands of Valentinian III and his mother Galla Placidia. After fighting against Aspar's army, Aetius managed to compromise with Galla Placidia. He sent back his army of Huns and in return obtained the rank of comes et magister militum per Gallias, the commander in chief of the Roman army in Gaul.
In 426, Aetius arrived in southern Gaul and took command of the field army. At that time Arelate, an important city in Narbonensis near the mouth of the Rhone, was under siege from the Visigoths, led by their king Theodoric I. Aetius defeated Theodoric, lifted the siege of Arelate, and drove the Visigoths back to their holdings in Aquitania. In 428 he fought the Salian Franks, defeating their king Chlodio and recovering some territory they had occupied along the Rhine. In 429 he was elevated to the rank of magister militum; this was probably the iunior of the two offices of comes et magister utriusque militiae, as the senior is known to have been the patrician Flavius Constantinus Felix, the most influential man in those years, and a supporter of Galla Placidia. In 430 the Visigoths led by Anaolsus attacked Arelate again but were defeated by Aetius. In May 430, Aetius and the Army accused Felix of plotting against him and had him, his wife, and a deacon killed. Once Felix was dead, Aetius was the highest ranking amongst the magistri militiae, even if he had not yet been granted the title of patricius or the senior command. During late 430s and 431 Aetius was in Raetia and Noricum, defeating the Bacaudae in Augusta Vindelicorum, re-establishing Roman rule on the Danube frontier, and campaigning against the Juthungi. In 431 he returned to Gaul, where he received Hydatius, bishop of Aquae Flaviae, who complained about the attacks of the Suebes. Aetius then defeated the Franks, recapturing Tournacum and Cambriacum. He then sent Hydatius back to the Suebes in Hispania.