Foreningen blev stiftet d. 19. marts 1936 under navnet Idrætsklubben Viborg, da de 35 medlemmer dyrkede både håndbold, svømning, gymnastik eller atletik. I 1939 blev foreningen dog omdøbt til Håndboldklubben Viborg og senere Viborg Håndboldklub, da håndbold havde den langt største tilslutning og interesse.
Spilledragten var dengang røde trøjer, blå bukser og hvide sko, som dog i 1941 blev ændret til grønne trøje og hvide bukser. Skoenes farve blev ikke nævnt. Den dag i dag er denne spilledragt stadig den officielle for Viborg HK på trods af brugen af de sorte shorts i dag.
Håndbold blev spillet udendørs på Eksercerpladsen i sommermånederne og i Eksercerhuset på Rødevej i vintermånederne. Der var ikke varme i salen og omklædningsrummene, og der var kun koldt eller ingen vand i hanerne.
Håndbolden stod i stampe under krigen, da tyskerne havde besat Eksercerhuset. Men efter krigen kom der gang i turneringshåndbolden, og da Viborg sammen med Holstebro havde de eneste indendørs haller i kredsen til brug til håndbold, spillede man næsten altid på hjemmebane. Men når man skulle på udebane, tog alle klubbens hold af sted samlet. Der var derfor tale om en heldagstur, når man skulle af sted.
Indtil 1960 var det højest rangerede hold serie 1. Men så kom der gang i oprykningerne. Herrerne spillede sig op i mesterrækken, og i 1963 bankede de på døren til 3. division. På damesiden skete der også noget. I jubilæumsåret 1961 avancerede de til mesterrækken, og i 1963 tog de ligeledes springet til 2. division. Siden dengang har begge hold aldrig været ude af divisionerne.
Disse oprykninger var vel også den egentlige årsag til en stor medlemsfremgang med flere tilmeldte hold til følge. Forholdene i Eksercerhuset var efterhånden blevet for trange, og da Gymnastikhøjskolen i 1961 tog sin hal i brug, fik seniorafdelingen henlagt sin træning og turneringskampe hertil. Flere hold krævede også flere trænere. Hidtil havde daværende formand Erik Bang trænet samtlige klubbens hold. Men det blev efterhånden for stor en mundfuld. I 1964 var trænerstaben vokset til 6, alle ulønnede trænere..
Faciliteterne i det gamle klubhus på Eksercerpladsen var nu også så elendige og utidssvarende, at man nu begyndte at kigge efter muligheder for at forbedre disse. Løsningen blev dog en nedrivning for at give plads til Tinghallen. Dermed var der også givet plads til et nyt spille- og træningssted. Men det var ikke ideelt, da gulvet ikke var velegnet til håndbold, og desuden blev mange aktiviteter aflyst pga. arrangementer i Tinghallen. Da Badmintonhallen så dagens lys, var man derfor hurtige til at lægge så mange turneringskampe som muligt over i denne. Træningstiderne kunne man ikke få.
Badmintonhallen var delvist blevet rejst ved hjælp af frivillig arbejdskraft, og nu så man i bestyrelsen en mulighed for på samme måde at få en hal, hvor man pga. de mange frivillige arbejdstimer ville have førsteret på timer i hallen. Efter lange forhandlinger med DSI, blev man enige om at bygge endnu en hal på betingelse af, at klubben leverede så meget frivilligt arbejde som muligt, ca. 800 timer. Formand Erik Bang noterede sig alene for halvdelen af disse timer.
D. 14. september 1970 blev der skrevet et stort nyt kapitel i Viborg HK’s historie, da DSI-hallen med nye og dejlige forhold blev taget i brug. Hallen er senere i flere omgange blevet renoveret og udbygget med cafeteria, klubrum m.m.