Die ersten Spuren der Besiedlung des Ortes, an dem das heutige Nesselsdorf entstand, sind in der frühen Steinzeit zu finden. Der nächstgelegene und wichtigste Ort mit Entdeckungen aus der Frühsteinzeit ist Štramberský kotouč. Um die Mitte des 13. Jahrhunderts gründete der Olmützer Bischof Bruno von Schauenburg das Schloss Schauenstein, gleichzeitig wurde das Dorf Nesselsdorf gegründet. Die Tatsache, dass Nesselsdorf in der sogenannten Mährischen Pforte liegt mit einer wichtigen Handelsroute, die den Handel zwischen der Ostsee und dem Mittelmeer sicherstellte, zeigt, dass dieses Gebiet bereits älteren Kulturen bekannt war.

Nesselsdorf blieb von Kriegen nicht verschont. 1621 wurde die Gemeinde von Wallachen angegriffen und geplündert. Noch in den späteren Jahren 1626 - 1716 litt Nesselsdorf unter dem Einfall der Dänen. Die Leibeigenschaftspflichten wurden verschlechtert, Häuser wurden verlassen, die Untertanen flohen aus dem Herrschaftsgut, die Erhöhung von Fronarbeiten nahm stark zu. Allmählich gab es Unruhe unter den Untertanen, denen es schwerfiel, die Verletzung ihrer alten Privilegien und Sonderrechte zu akzeptieren. Der erste große Aufstand war die Versammlung der Bauern am 19. Mai 1643. Nur dank der Verhandlungen der Bischofsbeamten mit den Untertanen endete der Aufstand mit einer Aussöhnung. Bis zum Ende des 17. Jahrhunderts kam es zu zwei weiteren Aufständen, die die Situation der Leibeigenen nicht verbesserten.

Auch im 18. Jahrhundert sehen wir die hiesigen schwierigen Untertanenverhältnisse. Besonders belastend waren die staatlichen Steuern, die während der Türkischen und Preußischen Kriegen stiegen. Diese Bedingungen führten zu einem weiteren Aufstand. Bischof Maximilian von Hamilton unterdrückte den Aufstand schließlich militärisch. Im September 1766 brach der Widerstand erneut aus. Die folgenden Verhandlungen dauerten bis 1773, als den Untertanen in manchen Punkten entgegengekommen wurde. Naturkatastrophen, Missernten, Epidemien, hohe Preise und Hunger haben die Menschen vor Ort schwer getroffen. Sie wurden durch Steuern belastet, die infolge der Napoleonischen Kriege stiegen.

Ein Wendepunkt in der Geschichte von Nesselsdorf war zweifellos die Gründung einer Fabrik für Steingut und Tonwaren im Jahr 1812. Im 19. Jahrhundert gründete Ignác Schustala in Nesselsdorf eine Kutschenfabrik. Zusammen mit der Entwicklung der Automobilindustrie und der damit verbundenen Zunahme der Anzahl der Arbeiter in Fabriken verlor Nesselsdorf allmählich seinen dörflichen Charakter und wurde 1910 zu einer Marktgemeinde. Der Bau des ersten Automobils war nicht nur ein weiterer wichtiger Markstein in der Geschichte des Unternehmens, sondern auch der Stadt. Bald nach dem Ausbruch des Ersten Weltkriegs nahmen die Anforderungen der österreichischen Armee an die Fabrik in Nesselsdorf zu, insbesondere bei der Nachfrage nach Lastwagen, und so zogen immer mehr Menschen in die Stadt. 1919 wurden die Fahrproben mit Wagen des U-Typs durchgeführt. Die Gebirgsbewohner verglichen diese Autos mit dem Gebirge Tatra. Der Name setzte sich durch und bereits im März 1919 verließen die ersten Autos namens Tatra den Betrieb. Die anschließenden Erfolge der Tatra-Fahrzeuge verbreiteten den Ruhm der Marke auf der ganzen Welt. Die bisherige Marktgemeinde wurde 1948 zu einer Stadt erhoben.

Zu den wichtigen Persönlichkeiten dieser Stadt zählen beispielsweise der Gründer der Tonwarenfabrik Ignác Rašek, der Fabrikbesitzer Ignác Schustala oder der Maler und Illustrator Zdeněk Burian.