Kráľ Matej nebol dokonalý, ako napokon žiadny človek z mäsa a kostí. Ale rozhodne nebol zlý panovník. Dokázal skonsolidovať Uhorsko ako málokto pred ním aj po ňom. Z relatívnej stability v druhej polovici 15. storočia ťažili aj Košice.
Kráľ si mesto, ktoré malo v tom čase takmer 10-tisíc obyvateľov, obľúbil, rád poľoval aj v okolitých lesoch. Na oplátku mu Košice vychádzali v ústrety aj v takých veciach, v ktorých by nemuseli. Matej sem dokonca istý čas na niekoľko mesiacov presunul kráľovský dvor.
Pred ťažením proti Turkom, ktorí vpadli do južných častí Uhorska, nechal v roku 1479 kráľovnú Beatrix z bezpečnostných dôvodov v Košiciach. Z toho vyplýva, že mesto muselo u kráľa požívať obrovskú dôveru. Skrátka, náklonnosť bola obojstranná.
Možno teda povedať, že počas panovania Mateja Korvína doslova platilo, že Košice sú slobodným kráľovským mestom. Užívali si kráľovu priazeň a zažívali rozvoj. Pravda, každá minca má dve strany. Niektorým šľachtickým rodom, viac či menej mocným, boli Košice tŕňom v oku. Pre objektivitu ale treba dodať, že aj mešťania občas zneužili svoje postavenie.
Kráľ Matej napríklad v roku 1482 poslal Imrichovi Zápoľskému list, v ktorom mu prikazuje, aby nedovolil do Košíc dovážať dolnozemské a sriemske vína, keďže trpkejšie hornouhorské nejdú na odbyt. S úsmevom možno konštatovať, že košické vína zrejme neboli veľmi kvalitné.
No späť k nepriazni šľachty, ktorá mala mesto aj jeho obyvateľov v zuboch. Prvým dôkazom o „vrelých“ vzťahoch je incident so Šemšeiovcami. Zakladateľom tohto rodu bol spišský kastelán Tomáš, ktorý kúpil časť obce Šemša aj s kostolom v rokoch 1322 až 1328.
Avšak Šemšeiovci mali majetky aj v Šaci. Konkrétne malý hrad – pevnosť. Vlastnil ju Frank Šemšei, ktorý čelil viacerým pokusom o zbúranie. Hrad bol tŕňom v oku Košičanov, keďže mal strategickú polohu na kopci, odkiaľ sa dalo dobre kontrolovať cestu do mesta od západu.
Frank Šemšei dostal úradný príkaz na jeho zbúranie v dôsledku nariadenia uhorského snemu ešte v roku 1445. Bolo to vzhľadom na obavy z bratríkov. O štyri roky neskôr uhorský snem oslovil mesto Košice s tým, že ak by hrozilo, že sa hrad môže dostať do rúk Jána Jiskru, má ho frank Šemšei zbúrať. Ak tak nespraví, majú to urobiť Košičania.
K tomu ale nedošlo. Košičania totiž využili príležitosť a v roku 1468 upozornili kráľa Mateja, že hrad stále stojí. Kráľ Košičanom odpísal v podobnom duchu, ako predtým uhorský snem. Ak Šemšei hrad nezbúra, môžu tak urobiť Košičania. Frank a neskôr ani jeho syn sa do toho pochopiteľne nehrnuli, a preto sa Košičania chopili šance a hrad zbúrali.
Šemšeiovci tomu nevedeli zabrániť. Z toho dôvodu pochopiteľne vzniklo medzi nimi a Košicami otvorené nepriateľstvo. Príležitosť na pomstu sa naskytla v roku 1482. Vtedy delegácia zástupcov mesta, kráľovho splnomocnenca a zopár členov jasovského konventu smerovala pre vybavenie nejakej záležitosti z Košíc do Jasova. Cesta viedla priamo cez Šemšu. Pri návrate späť do Košíc si na delegáciu v obci Šemša počíhali Ján, Ladislav a Viliam Šemšeiovci. Zajali ich, uväznili a poriadne zbili. Nezabudli ich aj okradnúť. Vzali dokonca aj cenné kráľovské listiny.
Odhliadnuc od toho, že Šemšeiovci napadli mešťanov z kráľovho obľúbeného mesta, to prepískli hlavne tým, že siahli aj na Matejovho splnomocnenca. Ponížením kráľovho človeka s osobitným postavením to už poriadne prehnali. Matej konal, hneď ako sa k nemu dostala informácia o incidente. Kapitánovi hradu v Dósgyóri Bernardovi Monellimu prikázal, aby násilím vzal Šemšeiovcom Šemšu a odobral od nich zadržané cenné písomnosti.
Dedinu mal držať vo svojej moci dovtedy, kým kráľ nerozhodne, čo ďalej. To však nebol v tých časoch jediný konflikt Košičanov so šľachtou. Čoskoro mali do činenia s omnoho mocnejším nepriateľom. Nebol ním nik iný ako vtedajší magnát Štefan Perényi, ktorý bol, okrem iného, hlavným županom Zemplína.
Začiatok otvoreného konfliktu možno datovať na 29. september 1483. Vtedy sa niekoľko Košičanov na vozoch s nádobami vybralo na oberačku hrozna do mestečka Szántó. Prechádzali cez dedinu Viszoly, ktorá patrila Štefanovi Perényimu.
Ten nahuckal svojho mýtnika Valenta a jeho družinu, aby Košičanov cez obec nepustili. Keď sa mešťania objavili na začiatku dediny, mýtnik ich zastavil, jeho ľudia začali zvoniť na poplach. Čo je horšie, Košičanov poriadne zmlátili. Niektorých až tak brutálne, že na následky zranení zomreli. Dokonca aj mestskému senátorovi a budúcemu richtárovi Jurajovi Ferberovi zlomili ruku. Košičania to pochopiteľne nenechali len tak a priamo ku kráľovi okamžite poslali sťažnosť.
Matej zareagoval tým, že Perényimu prikázal, aby do 32 dní prišiel pred kráľa vysvetliť okolnosti. Jasovský konvent poveril, aby prešetril celý incident. Lenže Perényi kráľovu výzvu ignoroval. To bol aj dôsledok rozdielneho prístupu. Perényi bol v šľachtickej i celkovej hierarchii určite vyššie ako Šemšeiovci. Tým pádom ho mohol súdiť iba sám kráľ.
Lenže Perényi aj naďalej robil prieky Košičanom. A nielen on. Celý rod Perényiovcov sa vzoprel kráľovi. Istý čas sa nezdráhali spolupracovať ani s bratríkmi. Napádali hlavne kráľových spojencov. Navyše Štefanov brat Mikuláš Perényi sa už správal ako lúpežný rytier. Využijúc svoje vojsko prepadával, obťažoval pocestných, kupcov, ktorí prichádzali z Poľska a terorizoval okolie. Matej chcel aj napriek tomu najprv celú záležitosť riešiť mierne a diplomaticky.
Podobne ako Štefana, aj Mikuláša Perényiho si predvolal k sebe. Mikuláš reagoval rovnako ako jeho brat – ignoráciou. Navyše svoje vyčíňanie „vyšperkoval“ tým, že prepadol a zabral hrad Stropkov, odkiaľ vyhnal posádku aj s tridsiatkárom, ktorý bol vlastne vyberačom daní. To už Mateja evidentne vytočilo. Ako kráľ si nemohol nechať brnkať po nose ani od magnátskeho rodu Perényiovcov.
No je zaujímavé, že so žiadosťou o rázne a tvrdé riešenie sa obrátil na Košičanov. Listom z 23. júna 1483 im prikázal, aby okamžite s celou svojou brannou mocou a vojenským vybavením obsadili kráľovský hrad Stropkov. Potom ho mali odovzdať naspäť kráľovskému tridsiatkárovi. Košičania kráľa ochotne poslúchli, veď Perényi bol aj ich nepriateľ, no nepochodili. Mikuláš navyše aj naďalej vystrájal tak, ako predtým.
Kráľ sa preto obrátil na jedného zo svojich dvoranov, Andreja Botha z Bajny, aby v Hornom Uhorsku zhromaždil ľudí verných kráľovi a spolu s nimi hrad dobyl. Matej sa obrátil aj na Košičanov a 7. októbra 1483 im poslal list s príkazom, aby Botha vo všetkom poslúchli. No krátko na to Mikuláš Perényi prekvapivo zomrel. Situácia sa ale nezlepšila. Mikulášových majetkov sa zmocnil jeho brat Štefan, ktorý prepadol Košičanov pri Viszoly. A nesprával sa o nič lepšie, ako Štefan.
Pokračoval v prepadoch a lúpežiach, tiež obsadil hrad Stropkov. Tu sa kráľ aj napriek prvotnému neúspechu zrejme znovu obrátil na Košice. A mesto zrejme poveril aj vyšetrovaním zločinov Štefana Perényiho. Matej Korvín totiž 29. novembra 1483 poveril Spišskú Kapitulu, aby Košiciam vystavila duplikáty príslušných kráľovských príkazov, ktoré sa za doteraz nejasných okolností stratili. Kapitula to dovtedy odmietala.
Kráľ informoval Košičanov o svojom ďalšom postupe. Aj o tom, že pod hradom Fiľakovo došlo ku konfliktu a dodal aj to, že Perényi verbuje do posádok hradov Šariš a Hrádok Poliakov. Košičania dostali pokyn podporovať kráľovho spojenca a schopného veliteľa Andreja Labatlániho. Mešťania mali zmobilizovať nielen svoje vojsko, ale aj obyvateľstvo vrátane služobníctva. Rovnako aj mestské povozy a hlavne kanóny, ktoré bolo treba na obsadenie troch hradov – Šariš, Stropkov a Hrádok.
Nemalo to byť zadarmo. Kráľ Košičanom sľúbil zaplatenie všetkých nákladov, ktoré vznikli. Tu treba spomenúť aj úlohu ďalšieho kráľovského mesta Sabinova, ktoré pomohlo pri dobýjaní Hanigovského hradu, ktorý tiež patril Perényimu.
Pomocou miest sa podarilo potlačiť vyčíňania Perényiovcov. Kráľ im odňal majetky a stratili aj svoje postavenie. Neskôr im síce boli vrátené, no bol to pre nich zdvihnutý varovný prst. Naopak, kráľ Matej sa východoslovenským mestám odvďačil. Osobitné postavenie mali mestá, ktoré boli združené v Pentapolitane. Vyčíňanie Perényiovcov ich vzťahy ešte viac utužilo.
A preto sa 11. apríla 1485 zišli zástupcovia Košíc, Prešova, Sabinova, Bardejova a Levoče v Prešove, kde uzavreli dôležitú dohodu o spoločnej obrane. Potvrdila sa však aj dôležitosť vzájomnej spolupráce s kráľom.
Matej Korvín si uvedomoval, že sa môže spoľahnúť na Košice, ale aj ostatné slobodné kráľovské mestá na dnešnom východnom Slovensku. Disponovali určitou ekonomickou a vojenskou dostatočnou na to, aby v tejto časti kráľovstva dokázali účinne pomáhať panovníkovi.
Matej mal veľmi dobrý vzťah ku Košiciam. Aj preto ho možno v tom čase nazvať „kráľom Košíc“ a mesto „kráľove Košice“.