Pokud jde o historii tohoto malebného městečka, první důkazy o osídlení dokazují, že toto místo bylo obýváno už ve starší době kamenné. Výzkum ukázal, že lidé této kultury vyráběli pracovní nástroje z různě barevného radiolaritu, který získávali v blízkosti hory Chmelová. První velkou událostí, která se zapsala do historie, bylo vybudování pozdněrománského královského hradu, ke kterému došlo v první polovině 13. století. Prvním zdejším purkrabím byl Smil ze Zbraslavi a Střílek.
Pro město bylo důležité také období první republiky, kdy zde byla postavena železniční trať. Město Brumov-Bylnice vzniklo 14. června 1964, kdy došlo ke spojení dvou obcí, a to Brumova a Bylnice. O rok později získala tato obec status města. Město se i poté dále rozšiřovalo, konkrétně 15. července 1976 se jeho součástí stal také Svatý Štěpán a 24. července 1997 slovenská část osady Sidonie.
Dobré podmínky pro osídlení tohoto kraje poskytovala především výhodná poloha. Toto místo se totiž nacházelo v blízkosti důležité obchodní cesty, tzv. Vlárského průsmyku, který spojoval Pováží s Pomoravím. V době, kdy vzrostl význam Vlárského průsmyku, byl nejspíše z důvodu ochrany obchodních styků, na návrší postaveno opevněné sídliště. Později byl na tomto místě vybudován kamenný hrad.
Širší osidlování jižního Valašska začalo ve 12. století, kdy bylo hradní návrší znovu opevněno. V této době byla s největší pravděpodobností zbudována také dřevěná stavba, která se stala přímým předchůdcem kamenného hradu.
Díky sporu mezi českými Přemyslovci a uherskými Arpádovci byl moravský markrabě a později český král Přemysl Otakar II. nucen zabezpečit zemské hranice. Významným rokem pro město Brumov se stal rok 1255, kdy se v jedné listině objevuje jméno Smil, purkrabí brumovský. Kamenný hrad se brzy po založení stal významným centrem východomoravské oblasti při Vlárském průsmyku. Své sídlo zde mělo mnoho šlechtických rodů.
S historií města je úzce spojen i král Vladislav II., který v roce 1499 povolil městu Brumov pořádat na den sv. Václava trhy a roční jarmark a v roce 1500 pak výroční trh. Městu udělil právo hradišťské a také povolil užívání pečeti.