To supplement Laurel' very useful answer, I offer a few more early instances of "uphill battle." From "American States," in Cobbett's Political Register (January 4, 1812):
Therefore, Mr. Foster, our Minister now in America, had scarcely taken time to eat his first dish of ham and fried eggs, when he began to complain of these invasions. He had an uphill battle to fight about the Orders in Council, and this complaint about the Floridas appears to have been looked upon as a sort of set-off or make-weight in the negociation. In short, he makes a regular and formal complaint, in the name of the Prince Regent (in behalf of His Majesty), of the occupation of the Floridas by the American States.
One interesting thing about this early instance of "uphill battle" is that the writer is using it figuratively—indicating that the longer phrase "fight[ing] an uphill battle" was already (in 1812) familiar to some people in its literal sense of having to fight on an uphill grade against an enemy deployed on higher ground.
From "Extracts from Hazlitt's Table-Talk: Cobbett," in The Saturday Magazine (October 20, 1821):
Mr. Cobbett is great in attack, not in defence: he cannot fight an uphill battle. He will not bear the least punishing. If any one turns upon him, (which few people like to do,) he immediately turns tail. Like an overgrown schoolboy, he is so used to have it all his own way, that he cannot submit to any thing like competition or a struggle for the mastery; he must lay on all the blows and take none.
Again, the usage is figurative, not literal. An interesting early instance of the expression appears in Pierce Egan, "Dick Curtis," in Boxiana; or, Sketches of Antient and Modern Pugilism (1824), where the expression is not explained but may involve engaging in a prize fight against a taller opponent:
RICHARD we look upon as the gem of the whole lot of CURTIS'S, inasmuch as his skill, science, and general mode of sparring, whether for offence or defence, is vastly superior to that of his brothers, without excepting Jack, who, although terminating his career, after having won in three uphill-battles (and losing two at great disparity), was denied the character of being a skilful boxer; yet again, if this position be true, it would add to his reputation for bottom: in truth he was all pluck from top to toe.
Egan, at any rate, refers to Dick Curtis later in the piece as "our game little hero," suggesting that none of the Curtis brothers were particularly tall. It is possible, however, that "fighting uphill" in English boxing of the 1820s referred simply to working one's way up through the ranks of would-be contenders by challenging more highly regarded fighters.
None of the earliest instances that turned up in my Google Books and Hathi Trust searches used the phrase "uphill battle" literally. Nevertheless, it seems reasonable to suppose that the first uses of the phrase were literal; and if that is the case, the expression must go back to some time before 1812.