Поселение Стиккисхоульмюр было образовано в 1550 году как торговая площадка (благодаря удобной гавани), созданная датскими и немецкими торговцами. Своё название поселение получило в честь небольшого острова под названием Стиккид (исл. Stykkið, букв. «кусок»).[1]

В 1596 году из-за Стиккисхоульмюра разгорелся конфликт между ганзейскими купцами из Бремена и графом Ольденбургским в связи с тем, что датский король Фредерик III продал обеим сторонам исключительное право торговли в Стиккисхоульмюре. В 1602 году, с введением датской торговой монополии, город переняли купцы из Мальмё, входившего тогда в состав Дании. С начала XVIII столетия право на торговлю в Стиккисхоульмюре перешло непосредственно к датской короне.[1]

После отмены датской монополии, в конце XVIII века, в городе селятся как исландские торговцы, так и датские купцы. В XIX столетии город быстро развивается. В 1838 году здесь открывается аптека, третья по счёту в Исландии. В 1909 году был расширен и модернизирован городской порт. В 1928 году в Стиккисхоульмюре садится первый самолёт, в том же году на улицах города появляется и первый автомобиль. В 30-е годы XX века в городе католическим орденом францисканцев основывается женский монастырь, при нём строятся больница и детский сад.[1]

В Стиккисхоульмюре сохранилось старинный архитектурный центр с краеведческим музеем и церковью 1878 года постройки. Здесь же находятся одна из старейших метеорологических станций Исландии (основана в 1845 году) и Музей воды.

31 мая 2009 года (в день Пятидесятницы) был официально открыт музей вулканов (исл. Eldfjallasafn) с показа выставки на основе коллекции исландского вулканолога с мировой известностью Харальдюра Сигюрдссона, уроженца этого города. Харальдюр[2] работал профессором вулканологии и океанографии в США, но затем переехал в Исландию после 40 лет работы за рубежом. Во время своих путешествий по всему миру он собрал большую коллекцию, связанную со своей научной деятельностью — различные произведения искусства, учебные материалы и книги, относящиеся к вулканическим извержениям и вулканической активности во всём мире[3].