Coney Island: Food & Dining by Jeffrey Stanton:

In 1867 Charles Feltman owned a pie-wagon that delivered his freshly baked pies to the inns and lager-beer saloons that lined Coney Island's beaches. His clients also wanted hot sandwiches to serve to their customers.

Feltman boiled the succulent pork sausage and placed between a roll. The wheel-wright tasted the it and liked it. Thus the hot-dog was born.