Bloody Mary designates a cocktail consisting of vodka, tomato juice and pungent flavourings, typically served with a celery stalk or similar garnish. This name dates back to 1939; the earliest instance that I have found is from the column The Voice of Broadway, by the American journalist Dorothy Kilgallen (1913-65), published in the Wilkes-Barre Record (Wilkes-Barre, Pennsylvania) of 25^th November 1939:

The Colby M. Chesters, 3^rd, are polishing up the bassinet . . . . Lupe Velez and Fifi d’Orsay, the long-time feuders have kissed and made up . . . . Newest hangover cure to entrance the headholders at “21”¹ is called a “Bloody Mary”—tomato juice and Vodka! . . . . Monte Woolley, the grease-paint Alexander Woollcott, is being profiled by writers on three magazines: Ernest Boyd for Town and Country, Russel Maloney for the New Yorker, and Jack Mosher of Colliers.

¹ the 21 Club, located at 21 West 52^nd Street, in New York City

But it had become fashionable to mix vodka with tomato juice earlier in the 1930s—although no name had been given to those cocktails; the earliest mention that I have found is from Standing By . . . Being the First of a Sequence of Weekly Outbursts on This and That, by “The Bystanders”, in The Bystander (London) of 7^th June 1933:

Freak drinks amuse us—only because we are light-minded about drinking; the true connoisseur deplores such “fancy messes.” A certain actress now livens up her tomato-juice cocktail with a tot of vodka. She may be seen rolling this concoction round her pretty mouth in a new bar near Portland Place². Others are drinking port with ice floating in it. No one has yet invented a sillier tipple than the shrimp-and-sherry cocktail of post-war Deauville; or a more perilous than the “green devil” of gin and crême de menthe with which the Chief Purser of the P. and O. once attempted to assassinate us in dem bad ole days.

² Portland Place, in Marylebone, London

Another early mention is from the column On Broadway, by Walter Winchell, published in The Cincinnati Enquirer (Cincinnati, Ohio) of 31^st March 1939:

The cast of the Hasty Pudding Show have a new form of mickey which doesn’t make them “ick” . . . It is Vodka with tomato juice.

The following mention is of a different nature; in A Place in the Country: The Story of a Great Adventure (Funk & Wagnalls Company – New York and London, 1936), Dwight Thompson Farnham (1881-1950) wrote that he spiked tomato juice with vodka in order to inebriate the Reverend Lowsley Threep, “a really militant Connecticut Temperance Crusader” who kept invading his domain (the author had moved from New York to Connecticut, where he had established a place of his own):

The next time the Reverend called unofficially, I slipped about a jigger and a half of vodka into a couple of tall glasses of tomato juice and told the maid to serve them at once. When they reached us in the garden I passed him one with the remark:
“I find tomato juice very refreshing after a strenuous day in the city. Made from our own tomatoes. Won’t you have one?” He took it and answered gallantly:
“Ah! Nature’s own nectar! I shall be delighted!”
[The preacher gets intoxicated; he is now about to depart.]
“But lesh I forget—my dear Christian bruzzer—will you pleesh procure me a cutting—a very little cutting of zat excellent tomato vine, zat vine from wich zis mos’ stimulating an’ refreshing beverage was prepared. I don’t know when I have expreshed myshelf sho clearly. I mush have a lil cutting from Naboth’s vineyard.”
As I returned from a hurried forage into the vegetable garden, I heard a cracked voice raised in song. He continued his song as I approached. I gathered it dealt with the love life of Nebuchadnezzar, King of the Jews. He received my offering with open arms, made three formal bows and marched hurriedly out of the garden gate, his arms full of tomato vines and his mouth full of song.