Miasto Nový Jičín zostało założone prawdopodobnie w latach 80-tych XIII wieku na skrzyżowaniu szlaków handlowych z Polski i Śląska do Czech i Węgier. Jego regularny układ sugeruje, że zostało założone „na zielonej murawie” jako centrum gospodarcze majątku Starý Jičín. Jednak najstarsza pisemna wzmianka o mieście pochodzi z 1313 r., kiedy to miasto otrzymało pierwsze prawa miejskie (myto) od króla Jana Luksemburskiego. W tym czasie miasto i folwark Stary Jiczyn należały do panów z Kravaře. W 1373 r. panowie z Kravaře nadali Nowemu Jiczynowi prawo do umierania, zezwolili na coroczny targ i dali podstawę do herbu miasta - zwiniętej strzały trzymanej przez uzbrojonego mężczyznę. Miasto było w ich posiadaniu do 1434 roku. W latach 1500-1558 właścicielami miasta i dworu stali się panowie z Žerotína, którzy zapisali się w historii miasta przede wszystkim przebudową pierwotnej gotyckiej twierdzy, wzniesionej pod koniec XIV wieku, na wygodną renesansową rezydencję. Dzięki rodzinie Žerotínów rozpoczęła się budowa kamiennych arkad i domów miejskich na rynku, ponieważ miasto było zbudowane z drewna aż do niszczycielskiego pożaru w 1503 roku. Nový Jičín bogacił się dzięki słynnej produkcji sukna, a w 1558 r., po odejściu Žerotínów, został wykupiony z poddaństwa i stał się miastem kameralnym.  W 1620 roku król Fryderyk Wielki uczynił miasto miastem królewskim. Wojna trzydziestoletnia przyniosła mieszkańcom bezprecedensowe trudności. Rok później w pobliżu Nowego Jiczyna miała miejsce wielka bitwa, podczas której miasto zostało zdobyte przez protestancką armię księcia Jana Jerzego Krnovskiego, a 500 neapolitańskich żołnierzy zostało zabitych na obrzeżach. Wielkie barokowe pożary w latach 1768 i 1773 poważnie dotknęły całe miasto, ale wkrótce Nowy Jiczyn wzrósł do swojej następnej formy. Miasto stało się siedzibą sądu okręgowego, budowa drogi cesarskiej przyniosła połączenia ze światem oraz rozwój przemysłu i handlu. W połowie XIX wieku do miasta powrócili Żydzi i powstały duże fabryki tekstylne, dzięki którym miasto do dziś nazywane jest „miastem kapeluszy”.

Istnieje kilka legend dotyczących nazwy Nový Jičín. Według jednej z nich miasto zostało nazwane na cześć Jitki, odważnej córki właściciela zamku Old Jičín, która walczyła z niedźwiedziem, aby uratować małego chłopca. Pasterz, jej przyszły mąż, uratował ją przed wściekłym rannym zwierzęciem. Jitka kazała wybudować kaplicę w miejscu, w którym została uratowana. Jej mąż zbudował obok niej domek myśliwski, poświęcony Jitce, czyli Jitčinowi, później Jičínowi. Inna teoria wywodzi nazwę miasta od słowiańskiego słowa dik, dzika, który był obfity w okolicy. Stąd najpierw Dičín, później Jičín.