I agree that it is a strange construction. So I thought maybe searching for why you might use the phrase "say die" (instead of "never say die") might shed some light on the origin of the phrase. The earliest publication I could find, in which the phrase "say die" was included, is a play called, "The Faithful Shepherd." The play was published in 1590, written in Italian by Giovanni Battista Guarini. The English translation wasn't published until 1647. In a 1736 edition of a book entitled The faithful shepherd:
A pastoral tragi-comedy, written in Italian by the celebrated Signor Baptista Guarini, there are these lines (pages 102 and 103):
"Let those fair amiable Eyes release
My Life, now bitter, which once made it sweet;
And those bright Stars, which my Love's Torches li't,
Light too my Funeral Tapers, and fore-run,
As once my rising, now my setting Sun.
But thou more hard than 'ere thou wert before,
Feel'st yet no Spark of Pity, but art more
Deaf to my Pray'rs. Must I then talk alone?
Wretch that I am, discourse I to a Stone!
Say die, at least, if nothing else thou' It say,
And thou shalt see me die..."
Within the next century, for whatever reason, the phrase "Never say die." becomes quite common. (I'm not saying it's a result of the play, by any means, in case anyone mistakenly thinks I'm implying that.) MetaEd mentions one citation in his answer, but there are many citations from the 1800s in which the phrase is used, including a flowery poem attributed to J.F. Waller, reprinted in Oddfellows' magazine, Vol. 13, 1881, page 91:
Never say die—never say die;
Life's worth the living, if we only try;
The hand and the brain
Were not given in vain.
We've a battle to gain,
And so—never say die.
Never say die—never say die;
If earnings be low and if living be high,
'Tis reason the more
Not to faint or give o'er,
Better days are in store,
And so—never say die.
Never say die—never say die—
When night is at darkest the morning is nigh;
Whether far off or near,
In God's time will appear
Some blessing to cheer,
And so never say die.
Never say die—never say die;
The soul that is steadfast may fortune defy;
In labour and art
Let the hand and the heart
Each do its own part,
And so—never say die.
Never say die—never say die;
When cowards despair, be this our reply—
All that's noble and human
In constant and true man,
In brave patient woman,
Cries—never say die.
Never say die—never say die;
Life is God's gift that we may not lay by;
Whatever befall,
'Tis the duty of all'
Till he gives the call
To say—never say die.