TL;DR Version: Yes, it was absolutely, without question, certainly legitimate, and in any case, there were no other potential claimants to compete with him.
Aragorn's claim isn't as strong as one might wish for, but it is unquestionably legitimate. And besides that, he has something his predecessors didn't - popular support, both among the commoners and the lesser royalty and nobles of Gondor and Rohan, and the Dúnedain of the North. And more importantly, he is the only option; unlike Arvedui's situation, there is no rival claimant. It's Aragorn or nothing.
The suggestion that Aragorn's claim is illegitimate rests on the idea that kingship in Gondor was solely dependent upon the male line, not the female line (i.e., father to son, not father to daughter). As we will see below, this simply isn't true - the lineage of the kings of Númenor, and their descendants in Gondor and Arnor, was legally passed down through both male and female descendants, although the former was usually preferred; this had "never [been] observed" in Gondor and Arnor, but there is no reason to believe it was no longer the law.
When Arvedui's claim to the throne was rejected on the basis of his lineage via a female, he made exactly this argument, and the Steward Pelendur and the Dúnedain, who were responsible for choosing the heir, didn't respond (because they knew he was right) - they simply chose his rival because they liked him more. This chain of events is impossible in Aragorn's case, because there is no one arguing against him, and his claim is unchallenged - he has no rival. If Gondor rejects Aragorn's claim, it is highly unlikely that it will ever be ruled by a king again.
Word of God:
Aragorn thus claimed the right to take the Orthanc-stone into his possession... because he was de jure1 the rightful King of both Gondor and Arnor.
- J.R.R. Tolkien, Unfinished Tales: The Palantíri
Obviously, this is enough to prove that Aragorn's claim was legitimate, but I've never let a simple sentence that amounts to a conclusive Word of God answer stand in the way of a long-winded diatribe, so I'll keep going.
Note: For a thorough study of Aragorn's ancestry, see Jason Baker's exemplary answer here: How much Elven ancestry does Aragorn have?
Aragorn's claim to the throne of Arnor can be traced through the tables of the Rangers, Kings of Arthedain & Kings of Arnor. His position as heir to the throne of Arnor is straightforward, for the line is unbroken back to Elendil, the founder and first ruler of the Northern Númenórean 'exile' kingdom. Although Isildur, Elendil's elder son, was first joint King of Gondor, he was on his way to take up the throne of Arnor when ambushed and slain following the death of his father, Elendil. By the time Andúril is reforged for Aragorn, Arnor had of course long since ceased to exist as a kingdom. There are also no other claimants, the lines of the kings of Rhudaur & Cardolan having failed.
Aragorn's claim to the throne of Gondor is less obvious. It rests upon his claim to be the rightful Heir of Isildur, and upon the right of Isildur's Line to claim the throne.
Isildur's departure from Gondor to take up the throne of Arnor following the death of his father, Elendil The Tall, left the throne in the hands of Anárion (his younger brother). From then on the royal lines of both kingdoms effectively split into the Northern and Southern Dúnedain. The distinction is made clear by the argument over the throne of Gondor which arose after the marriage of the last Arnorian king, Arvedui of Arthedain, to Firiel, daughter of Ondoher (the 31st king of Gondor). On the death of Ondoher and his sons, Arvedui believed this gave him sufficient reason to claim the throne of Gondor. The claim was rejected by the Council of Gondor, who chose Eärnil (a descendant of king Telumehtar). In the event, Arvedui could not pursue his case at the time.
Neverthless, Aragorn is the sole direct male descendent of the Line of Elendil. Moreover, Isildur did not renounce the throne of Gondor, which he held jointly with his brother.. The Southern Kingdom was originally divided into two, with Isildur based at Minas Ithil in Ithilien and Anárion at Minas Anor; the building of its capital at Osgiliath in the middle of the River Anduin was a compromise, albeit one which in practical terms could only serve as the demarcation point between the two parts whilst both brothers were present.
The case is clear: Aragorn's family tree proves that he is descended from both Isildur AND Anárion. His link to Anárion is through a female ancestor (Fíriel), and if there was a rival claimant who was related to Anárion through a male, Aragorn's claim would be the weaker. But there is no rival, so the gender of his ancestral link to Anárion is irrelevant.
Although this wouldn't have entered into the equation, it is still worth noting that Aragorn has blood not only from the Númenóreans, and not only from the elves via Elros - he also has Maiar blood in his veins. Jason Baker's brilliant answer here says:
Since Lúthien's mother Melian was a Maiar, we can use this same formula to determine that Aragorn is 1/(2^66)=1.355x10^-20=0.000000000000000001355% Maiar.
Considering Tolkien's statement that the Maiar (aside from Sauron) are essentially angels, Aragorn is part angel.
Arvedui, Eärnil, Anárion, and Isildur:
Arvedui's claim was rejected for a couple of reasons:
Because it was deemed (by the Dúnedain) to be inferior to the claim of Eärnil, by virtue of the latter's descent from Anárion; Arvedui, on the other hand, was descended from Isildur.
Because Pelendur the Steward, and the Dúnedain, liked Eärnil more.
On the death of Ondoher and his sons, Arvedui of the North-kingdom claimed the crown of Gondor, as the direct descendant of Isildur, and as the husband of Fíriel, only surviving child of Ondoher. The claim was rejected. In this Pelendur, the Steward of King Ondoher, played the chief part.
The Council of Gondor answered: "The crown and royalty of Gondor belongs solely to the heirs of Meneldil, son of Anárion, to whom Isildur relinquished this realm. In Gondor this heritage is reckoned through the sons only; and we have not heard that the law is otherwise in Arnor."
'To this Arvedui replied: "Elendil had two sons, of whom Isildur was the elder and the heir of his father. We have heard that the name of Elendil stands to this day at the head of the line of the Kings of Gondor, since he was accounted the high king of all the lands of the Dúnedain. While Elendil still lived, the conjoint rule in the South was committed to his sons; but when Elendil fell, Isildur departed to take up the high kingship of his father, and committed the rule in the South in like manner to the son of his brother. He did not relinquish his royalty in Gondor, nor intend that the realm of Elendil should be divided for ever.
'"Moreover, in Númenor of old the sceptre descended to the eldest child of the king, whether man or woman. It is true that the law has not been observed in the lands of exile ever troubled by war; but such was the law of our people, to which we now refer, seeing that the sons of Ondoher died childless."
To this Gondor made no answer. The crown was claimed by Eärnil, the victorious captain; and it was granted to him with the approval of all the Dúnedain in Gondor, since he was of the royal house. He was the son of Siriondil, son of Calimmacil, son of Arciryas brother of Narmacil II. Arvedui did not press his claim; for he had neither the power nor the will to oppose the choice of the Dúnedain of Gondor; yet the claim was never forgotten by his descendants even when their kingship had passed away. For the time was now drawing near when the North-kingdom would come to an end.
- JRR Tolkien, Gondor and the Heirs of Anárion
This boils down to two justifications for giving Eärnil the crown:
He was deemed the better of two candidates, according to the Pelendur Steward's and the Dúnedain's interpretation of the law
He was more popular. Note that Gondor didn't answer Arvedui's excellent argument - they just ignored him and gave the crown to his rival. They might as well have admitted the truth: "There is no reason to bar an heir of Isildur from the throne, and the suggestion that descent from Anárion is superior to descent from Isildur is silly - we just don't like you as much as we like him".
Neither of these factors can come into play against Aragorn, because he's the only potential heir, and he is almost universally loved.
Arvedui and Aragorn:
So why was Arvedui's claim rejected and Aragorn's accepted, despite the fact that Arvedui's claim was clearly much stronger? Simple:
Arvedui had competition, Aragorn didn't. The circumstances couldn't be more different: Arvedui vs. Eärnil; Aragorn vs. nobody.
- Arvedui's claim was deemed weaker than Eärnil's because Arvedui's lineage passed through a woman, and Eärnil's passed through a man. Although a male lineage was superior to a female lineage, and a firstborn son is superior to subsequent sons, this isn't relevant in Aragorn's situation, because a closer female lineage and a more distant male lineage is better than nothing at all. Aragorn is competing with no one.
Back then, the Steward Pelendur - the chief arbiter of Arvedui's claim - preferred Eärnil to Arvedui; now, the Steward Faramir supports Aragorn wholeheartedly.
- Were Denethor still alive, he would almost certainly have resisted Aragorn's claim, but he would just as surely be forced to step aside and accept Aragorn as king sooner than later, because there was a phenomenal amount of pressure for Aragorn to take the throne. But Denethor died, of course, and his son Faramir literally owes his life to Aragorn. Even if Aragorn hadn't saved Faramir's life, Faramir wouldn't have opposed him - Faramir is too humble and decent to do something as petty as denying Gondor its long-awaited king just to keep the Stewardship to himself.
The Dúnedain supported Eärnil and rejected Arvedui a thousand years ago, but now, they all support Aragorn and reject... not having a king at all.
- It appears that Arvedui never had the support of the Dúnedain; Aragorn does. Aragorn had the support of the Dúnedain of the North (i.e., the Rangers of the North) all along, and he led them for decades; the Dúnedain of the South (i.e., the Rangers of Ithilien, under Faramir) quickly came to support Aragorn when he showed his merits and defended Gondor. Thus, he had enjoyed the support of half the Dúnedain his whole life, and after Pelennor, he received the support of the rest.
Arvedui wasn't popular in Gondor, as far as we can tell, whereas Eärnil was a beloved and celebrated war hero; Aragorn is enormously popular in Gondor after Pelennor, and was indeed a (the?) hero of the battle.
- Arvedui wasn't particularly important to Gondor. We have no reason to think he had done anything for them, and he certainly didn't do as much for Gondor as Eärnil had. The people of Gondor knew that, without Aragorn's help, they would have been massacred.
The nobility and lesser royalty of Gondor appear to have supported Eärnil unanimously, and rejected Arvedui; the nobility and lesser royalty of Gondor (and even Rohan) unanimously support Aragorn.
- The account of Arvedui's attempt to claim the throne gives one the impression that he had no one on his side. We know for a fact that when Aragorn claimed the throne, everyone who mattered was with him - Prince Imrahil, King Éomer, Faramir the Steward, Lord Elrond, Lady Éowyn, even Gandalf. More on this below.
Pelendur and the Dúnedain felt that Arvedui's kingdom of Arthedain was less impressive than Eärnil's exploits as Captain of the Southern Armies against the Wainriders of Rhovanion, the Easterlings, and the Haradrim; Aragorn has achieved victories far more impressive than Eärnil's.
Although Aragorn has no kingdom (yet), which would appear to make him even less impressive than Arvedui, he is the clear heir to the throne of Arnor (once he reestablishes the kingdom of Arnor), and he has shown his prowess in countless battles, from the defense of the north to his service in the armies of King Thengel of Rohan, and Steward Ecthelion II of Gondor under the alias Thorongil (also acting as an advisor to Ecthelion II) - during this time, he attacked Umbar and defeated their superior forces, saving Gondor from ruin.
He led a series of campaigns that weakened Sauron, which would prove vital to the victory of the Men of the West over Mordor in the War of the Ring. He went into enemy territory in the East and South alone to '"explore the hearts of men good and evil" and learn about the "plots and devices" of the servants of the Dark Lord.' He led the Fellowship of the Ring. He destroyed the Corsair fleet at Umbar (again) and arrived to ensure the victory of Gondor and Rohan at the Battle of the Pelennor Fields.
He could have entered Minas Tirith and claimed the throne then, but chose not to, preferring to save the world first. Finally, he led the Army of the West in the Battle of the Morannon where he fought a force ten times the size of his own, giving Frodo the chance to destroy the One Ring, and ensuring the permanent end of the threat posed by Sauron and Mordor. He might not have a kingdom when he claims the throne of Gondor, but he has a legitimate claim, and he has the most impressive war record in the history of the world.
Aragorn' support base:
It’s pretty interesting comparing Arvedui and Aragorn, since the two were similar in that both were kings of Arnor (or would have been, in Aragorn’s case), and both made a claim for the throne of Gondor as well. Their reasoning was the same in both cases - Arnor was ruled by the descendants of Isildur. Gondor was ruled by the descendants of Anárion. Since Isildur and Anárion were brothers, one ruling family was related to the other. The difference between Arvedui and Aragorn, though, is how their respective claims were answered.
Arvedui made a claim for Gondor’s throne after the rightful king, Ondoher, died without any sons. Arvedui had even married Ondoher’s daughter, so part of his argument was that she should actually inherit the throne (with the assumption that he would be doing the actual ruling...) With Ondoher gone, the kingdom was being ruled by the Council of Gondor, lead by the steward Pelendur. It was up to them to decide who the next king would be. And Arvedui had a competitor - Eärnil, a distant relative of Ondoher and a military hero in Gondor.
Pelendur favored Eärnil, and eventually convinced the Council to choose him over Arvedui. Their reasoning was thus: Isildur had given up any control over Gondor, and so the heirs of Isildur shouldn’t have any claim to Gondor’s throne. And Arvedui’s wife couldn’t inherit since the throne could only be passed on to sons. Beyond that, at the time Arvedui’s kingdom had been reduced to the much smaller kingdom of Arthedain, which Gondor found to be rather unimpressive, especially compared to the heroic exploits of Eärnil.
Now, fast forward about a thousand years to Aragorn. In some ways, his claim to Gondor’s throne is even worse than Arvedui’s. He isn’t actually king of anything, and even Arvedui’s small kingdom has disappeared. But, unlike Arvedui, Aragorn has no competitors. There is no one else with any claim to the throne. Also, though it’s not the patrilineal inheritance that Pelendur wanted, Aragorn is technically a descendant of Ondoher through Arvedui’s wife.
While Pelendur proved that the steward did have the power to deny claims to the throne of Gondor, it’s likely that he wouldn’t have been able to do so if Eärnil hadn’t also been an option. Likewise, I think that (had Denethor survived), he might have tried to block Aragorn’s claim, but probably wouldn’t have been able to deny Aragorn indefinitely. His problem was that Aragorn was quite popular with many other powerful people. Gandalf may not have been too much help in Gondor’s political scene, but Prince Imrahil would have been. And, after Rohan literally swooped in and saved the day at the Battle of the Pelennor Fields, having Éomer’s support would have been helpful as well. And (while I may be biased in this) I have the feeling that Faramir would have supported Aragorn’s claim as well. And if the people of Gondor were impressed by Eärnil’s wartime exploits, then they would definitely have been swayed by Aragorn’s.
- Ask About Middle-earth
Denethor obviously intended to deny Aragorn the throne, and would probably have been justified in doing so. But after Denethor died, there was no one in a position of authority who was inclined to turn Aragorn away. Some of his supporters were quite powerful:
Éomer, King of Rohan
- As ruler of Rohan, and (following Theoden's death) the leader of the Rohirrim forces who had come to Gondor's aid at Pelennor, Éomer's support would have had a significant influence on Faramir and the commoners of Gondor.
Prince Imrahil of Dol Amroth, Denethor's brother in law
As Tolkien Gateway points out, "Imrahil recognized that Aragorn was the rightful King, but he agreed that it was wise for Aragorn to wait to enter the city, because he knew Denethor was strong-willed and proud."
Imrahil called on Aragorn to take the throne when he learned that Denethor was dead and Faramir (the new Steward) apparently dying; instead, Aragorn healed Faramir and convinced Imrahil himself to temporarily take over the Stewardship until Faramir recovered.
Faramir, Denethor's son and successor as Steward
Faramir was a good man, he owed his life to Aragorn, and he was humble enough to recognize that Aragorn was the king Gondor had been waiting for.
"Here is Aragorn, ...Elessar of the line of Valandil, ISILDUR's SON, Elendil's son of Númenor." - Faramir
Éowyn, Theoden's niece (and essentially, his adopted daughter), Éomer's sister, and later, Faramir's wife and princess.
- She loved Aragorn and knew he belonged on the throne; she would have been willing to convince Faramir to accept Aragorn's claim, if it was necessary to convince him (but obviously, it was totally unnecessary)
The remaining Dúnedain, both of the North and the South.
- Aragorn had been the Chieftain of the northern Dúnedain for decades, and when he came to Gondor's aid and saved the life of Faramir (Chieftain of the southern Dúnedain), he won their loyalty as well.
The Elves under Elrond.
- How is this relevant? Because the Kings of Númenor, and later Gondor, traced their lineage back to Elros. Aragorn was descended from Elendil, who was descended from Valandil, who was descended, several generations back, from Elros. Elros was the son of Eärendil and his wife Elwing, and the brother Elrond. Aragorn had Elrond in his corner saying "Your kingship is ultimately tied to descent from MY BROTHER, and I assure you, THIS IS THE GUY YOU WANT. He's definitely the dude who is most closely related to the first King of Númenor, my own brother".
Gandalf the White
- It goes without saying that Aragorn had Gandalf's support; although Denethor had probably turned the people of Gondor against "Mithrandir" due to his personal distrust of the wizard, the people quickly learned to love Gandalf when he led the defense of Minas Tirith.
And of course, the people of Gondor were firmly in Aragorn's camp - he had saved them, he had saved their beloved Faramir, and he was the only clear potential heir to the throne. They would have been thrilled by the prospect of having a king and an expanded kingdom again after a millennium of slow decline and loss of status, and the fact that Aragorn was also a noble, admirable, and heroic figure was the icing on the cake.
Word of God regarding the Palantíri:
The Palantír of Orthanc was the rightful property of the rightful king of Gondor:
These Stones were an inalienable gift to Elendil and his heirs, to whom alone they belonged by right; but this does not mean that they could only be used rightfully by one of these "heirs." They could be used lawfully by anyone
authorized by either the "Heir of Anárion" or the "Heir of Isildur," that is, a lawful King of Gondor or Arnor.
Other persons also were appointed to visit the Stones, and ministers of the Crown concerned with "intelligence" made regular and special inspections of them, reporting the information so gained to the King and Council, or to the King privately, as the matter demanded. In Gondor latterly, as the office of
Steward rose in importance and became hereditary, providing as it were a permanent "understudy" to the King, and an immediate viceroy at need, the command and use of the Stones seems mainly to have been in the hands of the Stewards, and the traditions concerning their nature and use to have been guarded and transmitted in their House. Since the Stewardship had become hereditary from 1998 onwards, so the authority to use, or again to depute the use, of the Stones, was lawfully transmitted in their line, and belonged therefore fully to Denethor.
It must however be noted with regard to the narrative of The Lord of the Rings that over and above such deputed authority, even hereditary, any "heir of Elendil" (that is, a recognized descendant occupying a throne or lordship in the Númenórean realms by virtue of this descent) had the right to use any of the
palantíri. Aragorn thus claimed the right to take the Orthanc-stone into his possession, since it was now, for the time being, without owner or warden; and also because he was de jure the rightful King of both Gondor and Arnor, and could, if he willed, for just cause withdraw all previous grants to himself.
- Unfinished Tales: The Palantírí
As if this wasn't clear enough, in Tolkien's Letter 246, he says that Aragorn won his contest with Sauron for mastery of the palantír because:
In the contest with the Palantír Aragorn was the rightful owner.
If the rightful owner of the Palantír was the rightful king of Gondor, and if Aragorn was the rightful owner of the Palantír, then Aragorn is the rightful king of Gondor (QED).
Aragorn has a legitimate legal claim to the throne; no one opposes him, and everyone supports him. His hereditary ties to the kingship are distant and relatively weak compared to the ties of previous kings, but that doesn't matter, because his ties are stronger and closer than anyone else on the planet. If Gondor had refused his claim, they would never have a king again; and as far as I can tell, Gondor had no legal right to deny his claim. The fact that they had no right to deny him coincided nicely with the fact that they had no desire to deny him (in fact, they were disappointed he made them wait until after the Battle of the Morannon - they wanted him to take the throne after the Battle of the Pelennor Fields, but he refused).
We can speculate about what might have happened if someone with a stronger claim to the throne had challenged Aragorn. Say someone who was descended from Anárion showed up and said that Aragorn's descent from Isildur made him a weaker candidate, and that this, combined with the fact that Aragorn's only ties to Anárion came through Fíriel, made him ineligible for the kingship of Gondor. This would be a sort of repetition of the Arvedui/Eärnil controversy, but with one important difference - remember that Eärnil won because of his war record. As noted above, Aragorn has the most impressive, one sided war record in the history of the world. This, compared with his distant but undeniable ancestral claim to the throne, would still tip the scales in his favor.
1de jure is defined as:
1. according to rightful entitlement or claim; by right.
synonyms: by right, rightfully, legally, according to the law
1. denoting something or someone that is rightfully such.
"he had been de jure king since his father's death"
mid 16th century: Latin, literally ‘of law.’