Origin of "uphill battle"
The Oxford English Dictionary dates the word in general back to 1548:
That countrey is full of vphilles and downhilles, & almost no parte of it euen, or plain chaumpian ground.
Udall's translation of Erasmus' Paraphrase
Not that much later, I was able to find examples of "uphill" being used to designate difficulty, sometimes more metaphorically than others:
Onelesse we meete with one, that will runne as swift vphill against nature, to do that which is good, as we all runne downe bancke, with the swinge of nature, to do that which is ill. Which when I finde, I will honour him, as I do none, though I do oft beare with some, in whome there appeareth but some shew of such a one.
Positions vvherin those primitiue circumstances be examined, 1581
Weare it soe that the matter hearin contained, weare such as did alltogeather runn with the Current of the tymes, I beleeue that I should get more grounde. with lesse tyme, and with lesse paines.
but in regarde that I am forced to goe vphill, I shall haue the more difficulty, and purchase lesse grounde then other waies, howeuer, my lyfe is not deare unto mee, I must runn or goe the rase that is set before mee
Winthrop papers, 1637
...hereste cannot be excused, the nature of it is to gather as it grows, it is to run downhil, and thats the cause why so many follow it and so few the truth, for its an uphill, a narrow way that leads to life, therefore few find it
Baby-baptism meer babism, 1653
Heavens way is uphill, and against heart; we are loath to enter the Gate, and more loath to proceed in the way to life
The hard way to heaven explained, 1662
The examples I found of "uphill battle" came later:
It takes up no falling cause; fights no up-hill battle; advocates no great principle; holds out a helping hand to no oppressed or obscure individual
The Edinburgh Review, 1823
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.