Anque la primer referencia escrita a la ciudá data de 1244, la so hestoria ye anterior. Los restos históricos más antiguos son fragmentos de cerámica que daten del sieglu XII, atopaos nescavaciones nel centru de la ciudá. Nun se sabe cuándo recibió Holstebro los privilexos de ciudá, una y bones la carta orixinal perder mientres dalgún de les quemes quhubo a lo llargo de la historia. Dende la Edá Media hastal sieglu XVII, Holstebro consistía dun conxuntu atarraquitáu de pequeñes cases, ente les cualos yera fácil quuna quema arrobinárase rápido. Les distintes quemes fueron la causa de que se perdiera la mayor parte de los edificios de la dómina medieval. En 1552, por casu, amburósel conceyu y perdiéronse los archivos de la ciudá.