Historia miasta sięga początków XVI wieku i panowania Jana Olbrachta. Ustrzyki zwane wówczas Ustryk zamieszkiwała wielokulturowa ludność. Choć okres wojenny zburzył dawniej panujący ład to wieś rozrosła się w piękne górskie miasteczko.
Historia powstania Ustrzyk Dolnych sięga II połowy XV wieku. Za panowania króla Kazimierza Jagiellończyka w 1496 r. miejscowość lokowano po raz pierwszy na prawie wołoskim. Na początku XV w. osada została przekazana pochodzącemu z Siedmiogrodu Iwonii Janczowiczowi Unichowskiemu. Dzierżawa wsi była nagrodą za zasługi dokonane podczas wojny bukowińskiej z Mołdawią. Wówczas za panowania króla Zygmunta I Starego, dnia 24 sierpnia 1509 r. nastąpiła ponowna lokacja wsi Ustryk. Nazwa osady pochodziła od wołoskiego słowa „ustrik” oznaczającego miejsce zbiegu rzek i potoków.
Wśród osadników znaleźli się nie tylko mieszkańcy z Węgier, ale i ludność pochodząca z ruskich wsi oraz wołoscy pasterze poszukujący bezpiecznego życia. Do Ustrzyk przybyli także Polacy i Niemcy. Osada znalazła się na rozwidleniu ważnych szlaków handlowych, prowadzących do Krosna, Sambora oraz na Węgry.
W 1727 r. król August II Mocny nadał Ustrzykom prawa miejskie. W tym okresie najliczniejszą grupę mieszkańców stanowili żydowscy kupcy. Do 1772 roku obszar ten należał do województwa ruskiego. Sytuacja uległa zmianie podczas I rozbioru Polski, kiedy to Ustrzyki Dolne znalazły się pod panowaniem austriackim. Dotąd prężnie rozwijające się miasto zaczęło przeżywać regres gospodarczy.
Ożywienie ośrodka miejskiego przyszło wraz z falą XIX-wiecznych przemian obecnych w całej Europie. W 1872 r. poprowadzono tędy strategiczną linię kolejową z Budapesztu do Twierdzy Przemyśl i Lwowa, a w rok później do Krosna i Jasła. Zaczęły powstawać dobrze prosperujące tartaki parowe, wybudowano obiekty sakralne: cerkiew greckokatolicką oraz kościół rzymskokatolicki, a także szkołę. Pod koniec XIX wieku ważną częścią przemysłu stała się ropa naftowa, a w latach 1900-1928 funkcjonowały w Ustrzykach dwie rafinerie.
W czasie I wojny światowej przez Ustrzyki Dolne przechodziły obce armie: oddziały carskie oraz austro-węgierskie. W okresie międzywojennym w pobliskiej wsi Ustjanowa Górna funkcjonowała szkoła szybowcowa oraz jedno z największych w Europie szybowisk. W wyniku wybuchu II wojny światowej miasto znalazło się pod okupacją sowiecką, a w latach 1941 – 1944 przeszło pod władzę niemiecką. W ciągu dwóch lat Niemcy doprowadzili do eksterminacji miejscowej ludności żydowskiej. Falę cierpienia i śmierci przyniósł również konflikt polsko-ukraiński.
Po II wojnie światowej Ustrzyki Dolne i okolice zostały włączone w granice ZSRR. W 1951 r. w ramach wymiany terenów przygranicznych miasto powróciło do Polski. Proces ten jednak wiązał się z przesiedleniem mieszkańców. Dotychczasowe społeczeństwo wysiedlono na wschód, a na ich miejsce przybyła ludność zza Buga. Na odzyskanych terenach powstał powiat z siedzibą w Ustrzykach Dolnych.