Mesto Veľké Kapušany vzniklo pravdepodobne pred 11. storočím, ako hraničné mesto tzv. živý plot, ktoré malo chrániť rázcestie a zohrávať úlohu brány, ktorá otvorí cestu do a z krajiny. Názov mesta sa odvíja od slova „kapu“ – brána, „kapus“ – brankár. Ten istý názov mal aj brod pri Kapušanoch, ktorá tvorila súčasť dôležitej cesty Leles-Veľké Kapušany-Užhorod.

Biskup Boleslav, zakladatel prepoštstva v Lelesi dostal obec Veľké Kapušany medzi ostatnými z okolia ako dar od svojho krstného otca, od kráľa Béla II, v roku 1132. Táto skutočnosť svedčí o tom, že obec už existovala pred tridsiatimi rokmi 12. str.

Najstaršie písomné zmienky o meste nachádzame v roku 1214. Mesto a jeho časti sú v týchto písomnostiach spomínané nasledovne: Copus, Chopus, Egházas Kapus, Kápolnás Kapus, Kys Kapus a Nagh Kapos. V hore spomínanom dokumente kráľ András II. zosilní právoplatnosť závetu Boleslava, v ktorom všetok svoj majetok prenecháva na rád premonštrátov a na cirkev Svätého Kríža v Lelesi. Vtedy ešte obec Kapušany sa spomína v listine ako COPUS.

Do polovice 14. storočia mesto bolo kráľovským majetkom. Počas týchto rokoch sa mesto rozvíjalo. Od kráľa László IV., kto panoval medzi 1272 a 1280, mesto dostalo mestské privilégia medzi ktoré patrilo aj právo organizovať trh. V roku 1342 kráľ Károly Róbert daroval Nevické panenstvo, tým spolu aj časť mesta Nagykapos Drugethovcom. Asi to zapríčinilo, že v roku 1344 sa začali boje o mesto medzi Drugethovcami z Humennej a biskupom Balázsom z Lelesu.