Gaden hed tidligere Stenkulsgade, fordi flere gader – bl.a. Sølvgade – i kvarteret Ny-København var opkaldt efter råstoffer, der bl.a. fandtes i Norge som dengang var den af det danske rige.
I 1677 fik København et særligt fængsel, Stokhuset, hvor de militære fanger blev anbragt. De civile der imod sad på Bremerholm.
I 1741 blev der opført et nyt Stokhus ved Østervold.
Navnet skyldes, at fangerne blev låst fast i ”stokke” med udborede huller. De såkaldt “uærlige” var bare anbragt i en celle, men de “ærlige” indsatte skulle udføre tvangsarbejde. Det var forbrydelsen der afgjorde, hvilken kategori man var i.
Tvangsarbejdet bestod f.eks. i vedligeholdelse af voldanlægget eller opførelse af offentlige bygninger, som f.eks. Amalienborg Slot. Fra stokhuset blev der leveret arbejdskraft til hele landet.
Der kunne være op til 50 fanger i en celle, og alle var lænket. Fangerne kunne indtil 1837 underkastes tortur.
I 1851 lukkede stokhuset, fordi man på den tid var i gang med en reform af det danske fængselsvæsen. 1862 søgte gadens beboere om at få gadenavnet ændret, fordi de ikke brød sig om at blive forbundet med de kriminelle beboere i stokhuset. Det lykkedes dog ikke.
I 1930’erne blev fængselsbygningerne revet ned, og i stedet opførtes Den Polytekniske Læreanstalt på grunden.
På hjørnet af Stokhusgade og Rigensgade ligger Jerusalemkirken.
