With reference to the practice of tossing a coin to determine a winner or to make a decision, the phrase heads I win (and) tails you lose means I win whatever happens.

In this phrase:
– the noun heads denotes the side of a coin which bears the figure of a head, i.e., the obverse side of a coin,
– the noun tails denotes the reverse side of a coin.

There existed an earlier phrase, cross I win (and) pile you lose, in which:
– the noun cross denoted the obverse side of a coin,
– the noun pile denoted the reverse side of a coin.

These are three occurrences of the phrase cross I win and pile you lose:

1-: From a dialogue between Carolina and Woodly in Epsom-Wells (London: Printed by J. M. for Henry Herringman […], 1673), a comedy by the English poet and playwright Thomas Shadwell (circa 1640-1692):

Caro. Since Marriage obliges men so little, and women so much; I wonder we endure the cheat on’t.
Wood. Y’are in the right, ’tis worse than cross I win, pile you lose.

2-: From Hudibras. In three Parts. Corrected, with several Additions and Annotations (London: Printed, and are to be sold by W. Rogers […], 1684), by the English poet and satirist Samuel Butler (baptised 1613 – died 1680)—the lawyer exposes a legal stratagem to his client:

Sir, quoth the Lawyer, not to flatter ye,
You have as Good, and Fair a Battery,
As heart can wish, and need not shame
The proudest Man alive to claim.
For if th’ have us’d you, as you say,
Marry, quoth I, God give you joy,
I would it were my Case, I’d give,
More than I’ll say, or you’ll believe.
I would so trounce her, and her Purse,
I’ld make her kneel for bett’r or worse;
For Matrimony, and Hanging here,
Both go by destiny so clear,
That you as sure, may Pick and Choose,
As Cross I win, and Pile you lose.

3-: From Some Remarks on the Barrier Treaty, between Her Majesty and the States-General (London: Printed for John Morphew […], 1712), by the Irish satirist, poet and Anglican cleric Jonathan Swift (1667-1745):

What is very surprising; in the very same Article where our good Friends and Allies are wholly shutting us out from Trading in those Towns we have Conquered for them with so much Blood and Treasure, the Qu— is obliged to procure that the States shall be used as favourably in their Trade over all the King of Spain’s Dominions, as Her own Subjects, or as the People most favoured. This I humbly conceive to be perfect Boys Play, Cross I win, and Pile you lose; or, What’s yours is mine, and What’s mine is my own.

The phrase heads I win (and) tails you lose is first recorded in The Second Essay on the Catholick-religion: Viz. On Its Suppression and the Substitution of Heathenism, or Idolatry (London: Printed for John Worrall, 1728), by Guy Vane—as quoted in the Oxford English Dictionary (online edition, March 2021):

Makes him play at Fools-game (even at Heads I win, and Tails you loose) with his Wealth and Substance.

These are the earliest occurrences of the phrase heads I win (and) tails you lose that I have found:

1-: From The Little Freeholder, a Dramatic Entertainment, in Two Acts (London: Printed for J. Murray […] and A. Guthrie […], 1790), by the Scottish lawyer and historian David Dalrymple (1726-1792):

“Reciprocity!” it sets my teeth on edge, it is so French: I suppose it is just as if he had said to me, “Heads I win, tails you lose.” I thought that it was against law; but this man, Lord they call him, quieted me with his reciprocity. Pay me for a bad action:—it was a bad action, a rich man to tempt a fellow over head and ears in debt: Fy, fy.—Pay me for a bad action, by getting for me what I had already by the justice of my General and my King; that is too much! I have been his cat’s-paw; yes, a silly rascally cat’s-paw!

2-: From The Life, Adventures, and Opinions of Col. George Hanger. Written by Himself (London: Printed for J. Debrett […], 1801), by the British army officer and author George Hanger (1751-1824), 4^th Baron Coleraine:

A good merchant is a good man; and a good man is a good merchant: it is also said, that a good mason is a good man, and that a good man also is a good mason. I do not dispute it; but it reminds me of sharpers tossing up for money with fools, and crying, Heads I win, Tails you lose.

3-: From Congressional Register. House of Representatives. Saturday, February 1. Debate on the Yazoo Claims, published in The Universal Gazette (Washington, District of Columbia, USA) of Thursday 5^th September 1805:

It was nothing more than a gambling match between the gamesters of the north and the gamesters of the south. For this time the south has won; perhaps the north may on the next gambling match recover or double their stakes. As to the speculators from the south, they had the advantage in the toss up; they said heads, I win, tails, you lose; they could not lose any thing for they had nothing at stake.