Whenever I read about the collapse of the western half of the Roman empire, I get a feeling of total collapse, as if no legions existed there anymore. The collapse of the empire would also mean no payment for the legionaries. I am surprised I read nothing about the legions existing at the time, as if none existed or that they simply vanished, without a bribe or promise of further employment. And what Roman legionary would fight for a barbarian king? Where were the legions in 476 AD?
The legions just became the armies of local warlords, they had been made up of local forces more loyal to their local leaders rather than Rome for a long time (centuries).
So in a sense they stopped to exist, in another sense they continued to exist, just under theoretically different high command.
But remember that the empire had for centuries been highly fractured, with each outlying region being more or less independent and minding its own affairs. Pretty similar in a way to how the EU was run in the 1970s and '80s, with some central command mostly on foreign policy level and a bit of economic coordination but otherwise independent fiefdoms.
And that situation persisted in Europe for centuries more, until finally the big players of the late middle ages consolidated several of the stronger of these fiefdoms each under a single ruler (France, England, the Holy Roman Empire).
The last vestiges of the Roman Empire itself moreover survived for quite a while after the fall of Rome as the Byzantine Empire, formerly the eastern Roman Empire, formerly the eastern provinces of the Roman Empire. And there were very real legions there for centuries to come (though in time they probably were no longer called that as the language lost ever more of the influence of Latin on it).
Rather than speculate from ignorance, I looked up one interesting chapter title on the relevant period from Gibbons: History of the Decline and Fall of the Roman Empire, to wit: Chapter XXXI: Invasion Of Italy, Occupation Of Territories By Barbarians.—Part I., and found this [my emphasis]:
The incapacity of a weak and distracted government may often assume the appearance, and produce the effects, of a treasonable correspondence with the public enemy. If Alaric himself had been introduced into the council of Ravenna, he would probably have advised the same measures which were actually pursued by the ministers of Honorius. 1 The king of the Goths would have conspired, perhaps with some reluctance, to destroy the formidable adversary, by whose arms, in Italy, as well as in Greece, he had been twice overthrown. Their active and interested hatred laboriously accomplished the disgrace and ruin of the great Stilicho. The valor of Sarus, his fame in arms, and his personal, or hereditary, influence over the confederate Barbarians, could recommend him only to the friends of their country, who despised, or detested, the worthless characters of Turpilio, Varanes, and Vigilantius. By the pressing instances of the new favorites, these generals, unworthy as they had shown themselves of the names of soldiers, 2 were promoted to the command of the cavalry, of the infantry, and of the domestic troops. The Gothic prince would have subscribed with pleasure the edict which the fanaticism of Olympius dictated to the simple and devout emperor. Honorius excluded all persons, who were adverse to the Catholic church, from holding any office in the state; obstinately rejected the service of all those who dissented from his religion; and rashly disqualified many of his bravest and most skilful officers, who adhered to the Pagan worship, or who had imbibed the opinions of Arianism. 3 These measures, so advantageous to an enemy, Alaric would have approved, and might perhaps have suggested; but it may seem doubtful, whether the Barbarian would have promoted his interest at the expense of the inhuman and absurd cruelty which was perpetrated by the direction, or at least with the connivance of the Imperial ministers. The foreign auxiliaries, who had been attached to the person of Stilicho, lamented his death; but the desire of revenge was checked by a natural apprehension for the safety of their wives and children; who were detained as hostages in the strong cities of Italy, where they had likewise deposited their most valuable effects. At the same hour, and as if by a common signal, the cities of Italy were polluted by the same horrid scenes of universal massacre and pillage, which involved, in promiscuous destruction, the families and fortunes of the Barbarians. Exasperated by such an injury, which might have awakened the tamest and most servile spirit, they cast a look of indignation and hope towards the camp of Alaric, and unanimously swore to pursue, with just and implacable war, the perfidious nation who had so basely violated the laws of hospitality. By the imprudent conduct of the ministers of Honorius, the republic lost the assistance, and deserved the enmity, of thirty thousand of her bravest soldiers; and the weight of that formidable army, which alone might have determined the event of the war, was transferred from the scale of the Romans into that of the Goths.
In summary, Rome in the guise of the ministers of its Emperor, Honorius, determined that it had no need of 30 thousand experienced veteran loyal troops because only Christian were suitable to defend the Empire; and divested itself of the services of those loyalists. So there were Legions a plenty, loyal and veteran, but they were at least in this instance told to go stuff themselves.
Only volunteer militias are loyal to home and country; professional standing armies are only loyal to their commander and their paymaster, and all of Rome's legions had been professional standing armies since Marius' reforms. This is a key reason for the US Military's standing order that POW's are forbidden to give parole to a captor - by forbidding parole (and continuing to pay them while POW) the military continues to be their paymaster, and thus continues to command their loyalty.
As noted in the quote above, because they were manned by pagans Honorius's ministers reneged on the contract to pay the Legions, thus effectively bequeathing them on Alaric, who was willing to pay them without any qualms about their beliefs. The Legions were always there, willing and perhaps even keen to remain loyal, but were rightly miffed at such repudiation. For a comparable more modern example, consider the causes of the Sepoy Mutiny in India in 1857:
The Mutiny was a result of various grievances. However the flashpoint was reached when the soldiers were asked to bite off the paper cartridges for their rifles which were greased with animal fat, namely beef and pork. This was, and is, against the religious beliefs of Hindus and Muslims, respectively.
By 476 CE there were no Western legions to speak of. When Theodosius I had died in 395 both parts of the Empire were still going strong and had big armies. However, the first decade of the 5th century set in train events which led to a vicious circle for the West:
barbarian incursions -> inept handling of them -> devastation of the Empire's tax base lands and barbarian settlement within them -> inability to pay for the armies -> more barbarian incursions...
For a while the West got along and staved utter disintegration by skilfully playing the barbarians against each other (Aetius was a past master at this game but there were others as well).
Then the barbarians toyed with the imperial throne and crown for a while (case in point: Ricimer) and in the end (476) just dispensed with the onerous formality of maintaining a superfluous Western emperor who controlled nothing.
Wikipedia has a big and serious article on the Late Roman Army where one can learn (almost) all one ever wanted to know about its ranks, pay scales, helmet types, etc. Unfortunately, this article stops short of explaining the collapse of the Western army, merely alluding to it briefly as in this passage:
An analysis of the ethnicity of Roman army officers named in the sources shows that in the period 350–99, 23% were probably barbarian-born. The same figure for period 449–76 officers, virtually all Easterners (as the Western army had largely dissolved) was 31%.