Počátky města a zvláště městského hradu v Novém Jičíně jsou spojeny se slavným českým šlechtickým rodem pánů z Kravař. Dodnes tento nevyvratitelný historický fenomén symbolizuje polovina zavinuté kravařské střely ve znaku Nového Jičína. A právě nejstarší dějiny města jsou základem dějin městského hradu a pozdějšího zámku. Město a jeho opevnění se s největší pravděpodobností konstituovalo za jejich vlády nad městem, ale nelze vyloučit ani ještě starší počátky města na panství Starý Jičín na konci 13. století.
Starší bratr městského hradu v Novém Jičíně, výšinný hrad Starý Jičín, vznikl pravděpodobně již za vlády olomouckých údělných knížat z panovnického rodu Přemyslovců na konci 12. století, jak nasvědčuje jeho český název. Poprvé se v psané historii objevuje v roce 1240 jako majetek porýnského šlechtice Arnolda z Hückeswagenu, povolaného tehdy do Českého království. Rod Hückeswagenů však hrad asi kolem roku 1260 ztrácí ve prospěch českého panského rodu z Pňovic, předků pozdějších pánů ze Žerotína. Za pánů z Pňovic se poprvé v roce 1278 jmenuje městečko Starý Jičín a pravděpodobně i založili město Nový Jičín.
Ve stejné době za vlády „železného a zlatého krále“ Přemysla Otakara II. se z Čech na Opavsko dostává předek pánů z Kravař Vok I. (zkrácená podoba jména Vojtěch). Byl to majitel města a hradu Kravaře a manžel Přemyslovy nelegitimní dcery Anežky z Kuenringu. Po vymření Přemyslovců v roce 1306 a nastoupení krále Jana Lucemburského v roce 1310 se po jeho boku opětně vynořují páni z Kravař, jmenovitě Vok II. jako majitel panství Starý Jičín, Helfštejn, Fulnek a Plumlov.
Město Nový Jičín je poprvé nesporně v historii doloženo v roce 1313, kdy mu český král Jan Lucemburský uděluje privilegium na výnos mýta ze zdejší důležité obchodní cesty. Je pravděpodobné, že o privilegium se přimluvil Vok II. z Kravař a rovněž je téměř jisté, že výnos mýta byl použit na výstavbu města a patrně i jeho hradeb. Půdorys města nás totiž nenechává na pochybách, že bylo založeno na tzv. „zeleném drnu“ s pravidelným půdorysem, téměř čtvercovým náměstím a pravoúhlou sítí ulic někdy před tímto datem. Jako významné městské sídliště mělo již od svých počátků aspoň dřevěné palisádové opevnění s příkopem a hliněným valem s tzv. plaňky (proutěným vyplétaným plotem). Stavba kamenné hradby byla finančně náročná a mohla trvat desetiletí.
Městský hrad v Novém Jičíně, jehož počátky se kladou do doby kolem let 1370 - 1380, nepochybně souvisel právě s výstavbou kamenných hradeb. Po výstavbě dvou bran Horní a Dolní a některých bašt byl městský hrad dalším důležitým prvkem městského opevnění. Po Janu I. z Kravař (zemř. asi r. 1370), členu dvora císaře Karla IV., dědili společně jeho synovci a Drslavovi (I.) synové Beneš III., Lacek Veliký, Vok III. a Drslav II. O něco později právě Vok III. a jeho syn Jan IV. z Kravař jako stoupenci moravského markraběte Jana Jindřicha dostávají za svou pomoc významné privilegium pro město Nový Jičín. V něm v roce 1373 městu udělili právo výročního trhu na sv. Ducha, postoupili plat z odúmrtě a 30 lánů polností v Loučce, Šenově a Žilině, stanovili výši městské daně na 80 hřiven grošů českých a povolili tzv. procesí s kříži. Je možné, že právě Jan IV. z Kravař si zvolil za své sídlo městský hrad v Novém Jičíně.
Po smrti Voka III. v roce 1386 ho dlouho nepřežil ani nejstarší syn Jan IV. Panství a dokonce město Nový Jičín si v roce 1398 rozdělili zbylí dva synové Vok IV. (zemř. roku 1406) a Lacek II., pozdější olomoucký biskup (zemř. roku 1408). Svědectvím tohoto rozdělení je dodnes městský znak města a ve své době to byla pečet' města právě z roku 1398. V jejím obraze ruka z oblaku drží polovinu zavinuté střely, tedy tzv. odřivousu, rodového znaku pánů z Kravař. V roce 1397 se rovněž město Jičín poprvé jmenuje Nový Jičín na rozlišení od Starého Jičína.
Na počátku 15. století zachvátilo českou společnost reformační úsilí po nápravě církve a celé feudální společnosti vedené Mistrem Janem Husem a jeho předchůdci. Významným podporovatelem Mistra Jana Husa se stal nejvyšší purkrabí pražský a moravský zemský hejtman Lacek Veliký z Kravař na Helfštejně (zemř. roku 1416). Právě on stál v čele hnutí české a moravské reformní šlechty o poskytnutí spravedlivého slyšení a poté protestního listu proti upálení Mistra Jana Husa v Kostnici v roce 1415. V roce 1412 hostil v městském hradě v Novém Jičíně polského krále Vladislava Jagielu. Feudální velmož Lacek Veliký, nejbohatší moravský pán, vykonával v letech 1408 - 1416 poručenskou správu nad dědicem starojičínského majetku sirotkem Voka IV. a to sice nad jeho synem Janem V. z Kravař. Ten se ujal svého dědictví až po vypuknutí husitské revoluce v roce 1421 a to panství Starého Jičína, Štramberka, Rožnova s Krásnem, Vsetína, Moravského Krumlova a později Fulneka.
Je téměř jisté, že během neklidné předhusitské doby za sporů moravských markrabat Jošta a Prokopa a zvláště za husitské revoluce byla dobudována městská kamenná hradba Nového Jičína včetně nárožního městského hradu v podobě půdorysu L s mohutnou nárožní čtvercovou věží. V přízemí dnešního zámku dosud nacházíme gotické kvádříkové zdivo a několik místností sklenutých gotickými valenými klenbami s úzkými okny. Jednoznačným svědectvím dobudování městského opevnění byl vojenský útok na město moravských husitů vedených Janem Tovačovským z Cimburka a vyvraždění jeho převážně německých obyvatel v roce 1427. Protože pobití obyvatelstva obležených měst prováděli husité pouze při delším branném odporu, je nesporné, že se město bránilo za hájitelnými kamennými hradbami. Jan V. z Kravař, zvaný tež lidem „pan Janek“, se sice ještě ubránil na svých hradech Starém Jičíně a Fulneku, nicméně moravskými husity založená blízká posádka v dobytých Odrách jej postupně donutila změnit názor i své vyznání. Nejméně od roku 1429 vystupuje Jan V. z Kravař na straně husitů po boku jak Jana Tovačovského z Cimburka, tak oderského velitele litevského knížete Zikmunda Korybutoviče, předtím husity požádaného českého krále. S oběma se v roce 1431 zúčastnil vítězné bitvy husitů s pátou křížovou výpravou u Domažlic. Patrně na zranění z boje původní katolík a spojenec protivníka husitů opavského knížete Přemka a poté kališník Jan V. z Kravař v roce 1434 umírá ve věku pouhých 28 - 30 let.
Po smrti posledního člena jičínsko-fulnecké větve pánů z Kravař se obrovské kravařské dominium se sídlem na hradě Starém Jičíně rozpadlo. Nejprve dědictví připadlo pánům z Cimburka a sice poručníkovi panu Ctiborovi z Cimburka na Křídle (zemř. roku 1437). Ten ovšem musel zadlužené panství do výše 4 700 kop grošů českých postupně rozprodat. Po jeho smrti se dokonce i hradu Starý Jičín na deset let zmocnil katolický loupeživý rytíř Jan Lapka z Oprostovic, přítel významného pohusitského kondotiéra v Uhrách Jana Jiskry z Brandýsa, který byl příbuzensky svázán s bývalými husitskými hejtmany ve Šternberku a v Odrách Vilémem Puklicí na Štramberku a Bočkem Puklicí na Drahotuších. Teprve v roce 1447 znovuzískal panství Starý Jičín kališník Jan z Cimburka na Křídle (zemř. roku 1472), který zčásti obnovil bývalé dominium přikoupením panství Rožnov, Vsetín, Uherský Ostroh, Drahotuš, Brumov a kláštera Vizovice.
Za vlády Jana z Cimburka nad městem máme první písemné svědectví o městském hradu v Novém Jičíně. V roce 1465 se ve velké síni tohoto hradu konalo významné zasedání lenního soudu z Kroměříže za přítomnosti olomouckého biskupa Tase z Boskovic o obnovení a propůjčení okolních biskupských lén. Bylo to v době, kdy na sousedních Hukvaldech skončila dlouholetá zástavní držba bývalých husitských hejtmanů Mikuláše Sokola z Lamberka, Jana Čapka ze Sán a Jana Talafúse z Ostrova. Hrad Hukvaldy přechodně držel český král Jiří z Poděbrad, a proto se zřejmě muselo konat zasedání biskupského lenního soudu v Novém Jičíně. Z této doby rovněž pochází část příčného křídla s gotickým arkýřem, uzavírajícím dnešní druhé nádvoří, jež bylo původně celé obklopeno zdí i vůči městu.
Po Cimburcích se po roce 1472 ještě ve vlastnictví panství a města vystřídali manželé dědičky Kunky z Cimburka Jindřich z Boskovic a Petr ze Svatého Juru a Pezinku. Další majitel od roku 1497 Jan z Kunovic zahájil brzy jednání s novou šlechtickou krví na moravském poli - pány ze Žerotína, kteří v roce 1500 panství i s hradem Nový Jičín získali do svého držení.