The word "frankfurter" comes from Frankfurt, Germany, where pork sausages similar to hot dogs originated. These sausages, Frankfurter Würstchen, were known since the 13th century and given to the people on the event of imperial coronations, starting with the coronation of Maximilian II, Holy Roman Emperor as King. "Wiener" refers to Vienna, Austria (German: Wien), home to a sausage made of a mixture of pork and beef.

Johann Georg Lahner, an 18th/19th century butcher from the Franconian city of Coburg, is said to have brought the Frankfurter Würstchen to Vienna, where he added beef to the mixture and simply called it Frankfurter.

The term dog has been used as a synonym for sausage since the 1800s, possibly from accusations that sausage makers used dog meat in their sausages.

Another possible origin for serving the sausages in rolls is the pieman Charles Feltman, at Coney Island in New York City. In 1867 he had a cart made with a stove on which to boil sausages, and a compartment to keep buns fresh in which they were served.

In 1871 Charles Feltman leased land to build a permanent restaurant, and the business grew, selling far more than just the "Coney Island Red Hots" as they were known.

A German immigrant named Feuchtwanger, from Frankfurt, in Hesse, allegedly pioneered the practice in the American midwest; there are several versions of the story with varying details. According to one account, Feuchtwanger's wife proposed the use of a bun in 1880: Feuchtwanger sold hot dogs on the streets of St. Louis, Missouri, and provided gloves to his customers so that they could handle the sausages without burning their hands. Losing money when customers did not return the gloves, Feuchtwanger's wife suggested serving the sausages in a roll instead.

An early use of the term hot dog in reference to sausage-meat appears in the Evansville (Indiana) Daily Courier (September 14, 1884): even the innocent 'wienerworst' man will be barred from dispensing hot dog on the street corner.

It was used "hot dog" to mean a sausage in casing in the Paterson (New Jersey) Daily Press (31 December 1892): the 'hot dog' was quickly inserted in a gash in a roll.

In another version, Antoine Feuchtwanger, or Anton Ludwig Feuchtwanger, served sausages in rolls at the World's Fair – either at the 1904 Louisiana Purchase Exposition in St. Louis, or, earlier, at the 1893 World's Columbian Exposition, in Chicago – again, allegedly because the white gloves provided to customers to protect their hands were being kept as souvenirs.

In the early 20th century, consumption of dog meat in Germany was common. The suspicion that sausages contained dog meat was "occasionally justified".

According to one story, the use of the complete phrase hot dog in reference to sausage was coined by the newspaper cartoonist Thomas Aloysius "Tad" Dorgan around 1900 in a cartoon recording the sale of hot dogs during a New York Giants baseball game at the Polo Grounds.

However, Dorgan's earliest usage of hot dog was not in reference to a baseball game at the Polo Grounds, but to a bicycle race at Madison Square Garden, in The New York Evening Journal December 12, 1906, by which time the term hot dog in reference to sausage was already in use. In addition, no copy of the apocryphal cartoon has ever been found.

Skinner's Restaurant, in Lockport, Manitoba, is reputed to be Canada's oldest hot dog outlet in continuous operation, founded in 1929 by Jim Skinner Sr.

Hot dogs are commonly served with one or more condiments. In 2005, the US-based National Hot Dog & Sausage Council (part of the American Meat Institute) found mustard to be the most popular, preferred by 32% of respondents; 23% favored ketchup; 17% chili; 9% pickle relish, and 7% onions. Other toppings include sauerkraut, mayonnaise, lettuce, tomato, cheese, and chili peppers. Condiment preferences vary across the U.S.. Southerners showed the strongest preference for chili, while Midwesterners showed the greatest affinity for ketchup.

The world's longest hot dog was 60 meters (197 ft) long and rested within a 60.3-meter (198 ft) bun. The hot dog was prepared by Shizuoka Meat Producers for the All-Japan Bread Association, which baked the bun and coordinated the event, including official measurement for the world record. The hot dog and bun were the center of a media event in celebration of the Association's 50th anniversary on August 4, 2006, at the Akasaka Prince Hotel, Tokyo, Japan.

On May 31, 2012, Guinness World Records certified the world record for the most expensive hot dog at USD$145.49. The "California Capitol City Dawg", served at Capitol Dawg in Sacramento, California, features a grilled 460 mm (18 in) all-beef, natural-casing frank from Chicago, served on a fresh-baked herb-and-oil focaccia roll, spread with white truffle butter, then grilled. It is topped with whole-grain mustard from France, garlic and herb mayonnaise, sauteed chopped shallots, organic mixed baby greens, maple syrup-marinated and fruitwood-smoked uncured bacon from New Hampshire, chopped tomato, moose cheese from Sweden, sweetened dried cranberries, basil olive oil and pear-cranberry-coconut balsamic vinaigrette, and ground peppercorn. Proceeds from the sale of each 1.4 kg (3 lb) super dog were donated to the Shriners Hospitals for Children.