The “Bloody Mary” cocktail is often accompanied by a celery stalk (or “celery stick”) stirrer. It is often stated that this combination was invented at Chicago’s Ambassador East Hotel in the 1960s, after a celebrity guest couldn’t find a swizzle stick and used a celery stick from a nearby garnish tray.
 
The true and verifiable origin of the Bloody Mary and celery stalk combination is unknown, but celery stalks were being served with tomato juice drinks throughout the 1950s, if not earlier. The Pump Room’s website of its own history does not mention the alleged Bloody Mary and celery stalk invention.
   
 
Wikipedia: Bloody Mary (cocktail)
A Bloody Mary is a popular cocktail containing vodka, tomato juice, and usually other spices or flavorings such as Worcestershire sauce, Tabasco sauce, beef consomme or bouillon, horseradish, celery, salt, black pepper, cayenne pepper, lemon juice, and celery salt.
(...)
In 1934, the cocktail was called “Red Snapper” at the St. Regis Hotel, where Petriot was hired at the time. It was here that tabasco sauce was added to the drink, and the name “Bloody Mary” eventually won popularity. In the 1960s it became popular to serve the cocktail with celery due to a guest at The Pump Room at the Ambassador East Hotel in Chicago.
 
Expedia.com
Ambassador East Hotel
Gold Coast hotel near Chicago’s Magnificent Mile
Pump Room
Featuring French-inspired cuisine, a notable wine list, and live music on weekends, the Pump Room has attracted celebrity guests for 65 years; the popularity of using a celery stick as a garnish in the Bloody Mary cocktail began here in the 1960s.
 
Pump Room History
Pump Room
1301 N. State Parkway
Chicago, Illinois 60610
312-266-0360
When Ernie Byfield opened The Pump Room in The Ambassador East Hotel on October 1, 1938, he undoubtedly had little idea that he was beginning an enterprise that would still be thriving to this day. Today, The Pump Room remains a magnet for movie stars and celebrities as well as a highly-acclaimed restaurant and Chicago landmark.
 
In 1938, Mr. Byfield was inspired by a place called the Pump Room that dominated the scene in 18th century England. Located in the resort city of Bath, The Pump Room was a place where Queen Anne and other stylish Londoners converged to revel in the social life at night after a long day. The Pump Room was named after the hot water drinks “pumped” into its patrons’ cocktails.
 
Byfield’s Pump Room was a success from the day it opened. Chicago’s socialites perched themselves along the large room’s western wall to observe the celebrities who made their appearances along the east side of the room. Those guests seated in Booth One, perhaps the more renowned table in the country, attracted the most attention.  Famed actress Gertrude Lawrence, who was starring in a play in Chicago at the same time as The Pump Room’s debut, established its reputation. Miss Lawrence staged a nightly gathering in Booth One during the play’s entire 90-day run. From that moment on, The Pump Room became the place to see and be seen.
 
John Barrymore roared for champagne; Bette Davis could be found curled up on the piano bench; Humphrey Bogart and Lauren Bacall celebrated their wedding in Booth One, as did Robert Wagner and Natalie Wood. Liza Minelli grew up in Booth One and has fond memories of dining there with her mother, Judy Garland. Ms. Garland immortalized the restaurant in the lyrics to “Chicago”, with the words “we’ll eat at The Pump Room/Ambassador East, to say the least”. And of course, Frank Sinatra held court in Booth One countless times.
 
After Byfield’s death in 1950, The Pump Room held on to its allure as a place for stargazing. A new generation of luminaries took up residence in Booth One. Mel Brooks personally greeted each guest; Paul Newman and Robert Redford lunched on ham sandwiches and pilsners every day during the shooting of “The Sting”. Michael J. Fox, Eddie Murphy and Jim Belushi have all continued the tables’ famous tradition.
 
Opera star Beverly Sills has added some high notes to the room, while a few rock and roll legends like David Bowie, Fleetwood Mac, Olivia Newton-John and Mick Jagger, have added some of their own. A little known drummer was refused entry when he failed to pass the dress code and titled his solo album, “No Jacket Required” after the incident. His name- Phil Collins. (He was sent a new jacket by way of apology.)
     
28 December 1951, Long Beach (CA) Press-Telegram, “Snack Tray Just Right to Serve Holiday Guests” by Mildred Flanary, pg. B3, col. 3:
These snacks make fine partners with mugs of tomato juice served piping hot. Garnish the juice with a slice of clove-spiked lemon; a generous spoonful of whipped cream; a slice of a large stuffed olive, a sprinkling of chopped chives; or a few pieces of popcorn for a gay holiday look. Celery stirrers add a bright finishing touch and are a conversation piece, too. At the last minute before passing steaming mugs of juice, add a short stalk of crisp celery with a few leaves left at the top. (No, they won’t wilt!)
 
24 January 1952, San Rafael (CA) Independent-Journal, ‘Big Drink Story—Canned Juice In History of Food Industry” by Zola Vincent, pg. 15, cols. 1-3:
The first tomato juice appeared in 1928 and was filtered so that it was as clear as apple juice.
(...)
One or two celery sticks in a glass of tomato juice is an eye-appealing touch. And the celery is pleasant, to crunch as you drink the juice.
   
28 January 1954, Modesto (CA) Bee, pg. 14, col. 2 photo caption:
Tangy vegetable juices are good to serve hot, topped with butter, as a snack in the afternoon or evening. Celery sticks are stirrers.
 
28 December 1957, Holland (MI) Evening Sentinel, pg. 5 ad:
Crimson tomato juice makes a colorful beverage accompaniment. Try serving it piping hot. Just before serving, add a short stalk of crisp celery for a “stirrer.”
 
29 July 1958, Galveston (TX) Daily News, pg. 3, col. 7:
For a tangy and tasty beverage, season a can of tomato juice with canned or bottled lime or lemon juice, celery salt, a dash of Tabasco and thick meat sauce; chill. Serve in cups with celery sticks as stirrers, if desired.
 
23 December 1958, News Castle (PA) News, pg. 11, col. 3:
When cocktails are served to guests before dinner, be sure to include glasses of chilled tomato juice for those who do not drink alcoholic beverages. Never serve a highly seasoned tomato juice cocktail unless you know the taste preference of guests. A crisp sliver of celery in the glass, as a stirrer, is good munching. It pleases children to be included in this pre-dinner cocktail service.
 
29 June 1960, San Mateo (CA) Times, pg. 24, col. 6:
It’s (Hot deviled eggs—ed.) shown here as the feature of an informal snack, accompanied by mugs of hot tomato juice with celery stick stirrers, and a bowl of corn crisps.
   
6 June 1963, Frederick (MD) News, pg. 17, col. 4:
Garnish with a cucumber disc on the edge of each glass or use a celery stick as a stirrer.
(“Pink Buttermilk Smoothie” made with buttermilk, tomato juice and Worcestershire sauce—ed.)
 
18 August 1966, San Antonio (TX) Light, pg. 56 ad:
Nacs Tomato Cup
Heat canned vegetable juice cocktail. Serve in “old-fashioned” glasses; float one

on top each glass; use celery stalk for stirrer. Serve with additional Nacs Round Corn Chips.
   
19 March 1968, Long Beach (CA) Press-Telegram, “Fizzes give zing to Sunday morning” by Ellen Krec, pg. B8, col. 7:
BLOODY MARY MIX
1 qt. of tomato juice
1 tsp. black pepper
2 tsp. Worcestershire sauce
1 oz. lemon juice
1 tsp. Accent
1 tsp. celery salt
Let stand overnight. Add your own vodka or gin and a celery stick stirrer.
   
2 December 1970, Syracuse (NY) Herald-Journal, pg. 8, col. 3:
Strain into glass and serve with a celery swizzle stick. Makes 1 Bloody Mary.
 
27 December 1972, Long Beach (CA) Press-Telegram, pg. F6, col. 3:
Or add a crisp celery stirrer.
(To a “Bloody Bernstein,” a Bloody Mary variation—ed.)
     
11 March 1973, San Antonio (TX) Light, “Hollywood Profile” by Dorothy Manners, magazine, pg. 25, col. 1:
He (Jimmy Stewart—ed.) gave his Bloody Mary a poke with the celery stick and came up with,...
 
23 October 1974, CUmberland (MD) Evening Times, “Celery Stick, Bloody Mary Companions” by Tom Hoge (AP Newsfeatures Writer), pg. 18, col. 4:
One day not long ago, the story goes, a young lady ordered a Bloody Mary in a Chicago cocktail lounge. When she noticed the swizzle stick was missing, she took a celery stalk from a nearby relish dish and stirred her drink. It did something for the flavor, and the management began serving celery sticks with all the Bloody Marys.
 
True or false, it marks one more use for this versatile vegetable that has long been a standy fo dieters, a base for salads and a prime ingredient for stews and soups.
 
Google Books
Classic Cocktails
By Salvatore Calabrese
Published by Sterling Publishing Company, Inc.
1997
Pp. 85-86 (Bloody Mary):
The origins of the celery stick garnish date back to the 1960s and are attributed to the inventiveness of a guest at The Pump Room in the Ambassador East Hotel, Chicago. The guest was served a Bloody Mary without the customary swizzle stick, so she picked a celery stick from a nearby garnish tray and used this to stir the drink. The maitre d’ noticed, hence the celery stick garnish was born. Should one eat it? Yes, if you are hungry. Otherwise, stir and put to one side. Many bartenders prefer not to add the celery stick.