За Гостивар се преплатени многу легенди од различни периоди. Според единствениот документ од античкиот период на историчарот Тит Ливи (59 п.н. ера-17 п.н.ера) се вели дека ...

последниот цар на Македонија, Пасаи (179-163) со 10.000 војници по усвојувањето на Ускана (Кичево) го освојува градот Драудак за подоцна да го освои Онеј (тетово). Од овие податоци може да се претпостави дека стариот град Драудак кој што имал голема важност, се наоѓа меѓу Кичево и Тетово, на местото на сегаѓен Гостивар.
Според една легенда сегашното има на градот Гости-гости, настанало за време на владетелот Букашин. Бидејќи доаѓале голем број на посетители, гости низ овие краишта, во текот турското владеење на турски го нарекувале „Гостивар“ што значи (гости има). Самото име, односно Гостивар се нарекуваше местото на собирање на гости т.е.„Градот на гостите“.

Во 1850 година геологот и балканологот Ами Бег во описот на Тетово меѓу другото во еден дел вели дека во Полог се наоѓа „големото село“ Гостивар , додека како град Гостивар по прв пат се спомнува во двата записи од 19 век . Според нив оваа населба на Полог ја има оформено својата чаршија (плоштад) додека вторникот бил пазарен ден. Во 1874 год. градот имал 400 куќи , околу 2000 жители , додека на крајот на истиот век 3500 жители.
Врз основа на записите на Абдулаќим Догани , Гостивар го добива името од девојката дојдена од Бар која што за место на живеење го има одбрано овој град. На локален јазикдевојка е гоца и тоа од Бар (Тивар) , затоа произлегува името Гостивар од момата од Тивар.

http://www.gostivari.gov.mk