Owned by Dave Magnuson, the restaurant had been located inside the first floor food court of the Northstar Center office complex from 1991 to 2023, though it relocated to a different retail space within the same building in 2021.

The restaurant's menu consisted of mostly hot dogs, made with Vienna sausage and including Chicago-style, in addition to nachos, pretzels, and ice cream.

Following the effects of the COVID-19 pandemic and nearby George Floyd protests, the restaurant experienced a significant loss in customers beginning in 2020, and as a result of Northstar Center's renovation project, Walkin' Dog closed on April 21, 2023.

Walkin' Dog originally occupied the smallest stall in the Northstar Center's lower level food court, in a 250 square feet (23 m2) space adjacent to the building's interior hotel entrance.

[2] Rachel Hutton from the Star Tribune described its offbeat location as being "wedged into a dark corner", while Minnesota Monthly's Susan Du compared it to the size of a postage stamp.

[2] A 2019 article from the same publication noted that despite downtown Minneapolis' decrease in popularity for typical fast food spots, Walkin' Dog was an exception and still offered menu items for $2.45.