The “frankfurter” is associated with Nathan’s (of Coney Island) and New York City, but the name comes from the city of Frankfurt (or Frankfort), Germany. The term “Frankfort sausage” has been current in New York since at least 1861. The food has been popular with German immigrants.
 
See also “hot dog.” 
   
   
(Oxford English Dictionary)
frankfurter
[G. Frankfurter wurst Frankfurt sausage. Cf. FRANKFORT.] 
A highly seasoned smoked beef and pork sausage, originally made at Frankfurt am Main.
[1877 E. S. DALLAS Kettner’s Bk. of Table 317 In the absence of Chorizos use Frankfort sausages.] 1894 San Francisco Midwinter Appeal 17 Feb. 2/1 Four bits for a Frankfurter seems rather steep.
       
Newspapers.com
23 December 1848, Manchester (UK) Examiner and Times, pg. 1, col. 5 ad:
M. LESSER, 51, 51, and 57, Cross-street, King-street, has constantly on hand, fresh, a supply of London Native OYSTERS, in barrels of various sizes, Brunswick and Frankfort SSAUSAGES of the best quality.
   
22 March 1859, Mineral Point (WI) Weekly Tribune, pg. 4, col. 2 ad:
FRED K MOELLER’S BEER HALL
(...)
FRANKFORT SAUSAGES,
At 20 cents per pound.
 
Making of America
9 March 1861, Vanity Fair, pg. 117:
My right shoulder is very high in the air, but it is elevated in order to sustain as much as possible the weight of my arm, which is like a Frankfort sausage.
   
Google Books
Travels on Horseback in Mantchu Tartary
by George Fleming
London: Hurst and Blackett
1863
Pg. 77:
...so on Frankfort sausage we fell back, and what with its excellent flavour, its delectable taste, and its unimpeachable substantial qualities, aided by capacious bowls of pearly rice…
 
10 December 1866, Brooklyn (NY) Daily Eagle, pg. 1:
A duel is expected in Paris between a journalist and a novelist. The former compared the latter to a Frankfort sausage.
   
19 November 1867, San Francisco (CA) Bulletin, pg. 1 ad:
MEYER’S
EXCELSIOR BRAUNSCHWEIGER
WURST, (SAUSAGE,)
MADE IN SONOMA OF GRAIN-FED PORK.
Schlackwurst, Mettwurst, Frankfurter,...
     
Making of America
Across America and Asia
by Raphael Pumpelly
New York: Leypoldt & Holt
1870
Pg. 370:
...we put into the cauldron one tin each of the following canned provisions: peas, beans, ox-tail soup, mock-turtle soup, Frankfort sausages, salmon, and tomatoes.
     
Newspapers.com
31 October 1871, Daily Press and Herald (Knoxville, TN), pg. 2, col. 3 ad:
JOS. FANTZ’S
Steam Sausage Factory.
(...)
FRESH AND SMOKED FRANKFURTER
 
Making of America
12 April 1873, Appletons’ Journal, pg. 494:
In Munich and Salzburg, for example, they serve you with “Vienna sausage;” your penetration concludes, therefore, that Vienna is the land of sausages par excellence, and you are consequently greatly surprised to find that, although sausages may be easily had in Vienna, they are, nevertheless, not half so abundant as in the places named; and, furthermore, when you get them, they are not “Vienna,” but “Frankfort” sausages.
   
8 November 1873, Sioux City (Iowa) Daily Journal, pg. 4:
Oyster stews, Frankfort sausages and sauerkraut at Rhinelander Hall this evening.   
   
29 July 1874, New Hampshire Patriot, pg. 4:
Prussia is responsible for Wagner’s opera, the Frankfort sausage and nearly all of our resident beer saloon keepers.
 
6 December 1879, National Police Gazette, pg. 14:
You have doubtless heard about the inexperienced husband who came home at the milkman’s hour deathly sick, and who, upon being interrogated by his wife, owned up to sixty beers during the night, and laid the sickness to one Frankfurter sausage. They always did disagree with him.
 
1885 New York’s Great Industries_, pg. 264:
Albert Peiser, Curator of Choice
Beef, No. 1361 Third Avenue.—A house exclusively devoted to the curing of the best and choicest cuts of beef, etc., is that of Mr. Albert Peiser, who established this enterprise in 1880.  He deals extensively in smoked and pickled tongues, briskets, Frankfurters, Viennas, bolognas, boulard and cervelat.
 
14 December 1885, The Cook, pg. 6, col. 1:
“FRANKFORT SAUSAGES—These sausages, being smoked, are very appetizing, and quite appropriate for the American table at this season. While they are characteristically a German dish, they may be made more healthful by much longer cooking than is usually given them. Our German brethren are quite satisfied with ‘Frankfurter’ cooked but a few minutes, but as these sausages contain pork, they, in my opinion, require twenty minutes’ boiling. A very nice way of cooking them is to heat them in a hot frying pan in a few minutes, then add boiling water, and boil them rapidly until done.  If they can be steamed they will be found excellent.”
 
4 March 1887, The American Israelite (Cincinnati, OH), pg. 9, col. 6 ad:
L. M. HELLER’S
(“Kosher” in Hebrew—ed.)
XLCR
Frankfurter Sausages
AND BOLOGNAS
Pickled and Smoked Meats, Tongues, Etc.
300 East 77th St.,
EAST OF SECOND AVENUE—NEW YORK
 
8 April 1887, The American Israelite (Cincinnati, OH), , Pg. 10, col. 3 ad:
(“Kosher” in Hebrew flanks this name—ed.)  Nathan Heldman,
N. E. Cor. 6th and Smith Sts, CINCINNATI, O.
DEALER IN
Kosher Meats only.  Smoked Beef and Sausage.  Pickled Beef, Tongues, Frankfurter Wurst and the “a la Schweinfurt” sausage, put up expressly for family use only.
   
15 November 1887, Bismarck (ND) Daily Tribune, pg. 4:
The shopgirl or milliner’s assistant in Munich will trip into the neighboring beer hall at noon, and take for luncheon a quart mug of beer and a piece of bread and a radish. (...) For dinner she has probably consumed the second or third quart of beer since morning and a Frankfurter sausage sandwich.
 
14 July 1889, New York (NY) Herald, “Coney Island,” pg. 6, col. 3:
THE FRANKFURTER SANDWICH.
The proper thing to do when you reach Coney Island, unless you want to be a marked exception and be considered an aristocrat, is to eat some Frankfurters. You will find the sausage sandwich man on every side. He makes the air vocal with his cries, and the odor of his sizzling sausage is so strong that you can cut it with a knife.
 
The first thing I saw when I came ashore at the pier was a sausage sandwich stand, where the proprietor was making a great deal more noise over his business than I thought it required, considering the size of the stock.
(...)
I then turned my attention to the Frankfurter. The chill had been taken off it by toasting it over a charcoal brazier and it was handed to me in the cleft of a wheaten roll. I was advised that the proper way to prepare it for deglutition was in a poultice of a chrome brown stuff called “German mustard.” When you are hungry a boiled sausage with dabs of mustard on it isn’t so bad to take at Coney Island, but if you are accustomed to eating at Delmonico’s you may not like it.