Das NS-Regime schuf ein dicht verzweigtes System zur Verfolgung, Bestrafung und Ermordung von Jüd:innen, Sinti:zze und Rom:nja und anderen „unerwünschten“ Personengruppen sowie von politischen Gegner:innen.
Die geheime Staatspolizei (Gestapo) bildete zusammen mit dem NS-Lagersystem und der NS-Justiz sowie der Wehrmacht und den Standgerichten ein ineinandergreifendes Instrument der Vernichtungspolitik des NS-Regimes. Zu den Aufgaben der Gestapo gehörte auch die Aufrechterhaltung von kriegswirtschaftlichem Arbeitszwang und die Überwachung von Zwangsarbeiter:innen. So schalteten Betriebe die Gestapo ein, um gegen missliebige Arbeiter:innen vorzugehen, wobei diese verwarnt, inhaftiert, misshandelt, an Gerichte überstellt und in vielen Fällen in Konzentrations- und Vernichtungslager überführt wurden.
Die Methoden der Verfolgung waren Inhaftierung, Folter und Mord. Der Einsatz von Spitzeln und die Mitwirkung von Denunziant:innen aus der Bevölkerung führten oft zu Verhaftungen. Ein Beispiel ist die Geschichte von Richard Ott. Nach einem ersten Versuch, aus der Wehrmacht zu desertieren, kam er 1944 in ein Wehrmachtsgefängnis in Polen, aus dem er flüchtete und sich in Krems bei Freunden der Familie versteckte. Dort traf er auf einen ehemaligen Schulkollegen, der ihn bei der Kriminalpolizei denunzierte. Er wurde erneut festgenommen und bei einem weiteren Fluchtversuch vom Wehrmachtshauptmann Franz Hahn am Pfarrplatz erschossen.
Der Gestapo gelang es auch, Spitzel zur Überwachung des kommunistischen Widerstands einzusetzen. Nach mehreren Verhören wurden drei zentrale Personen des Kremser Widerstands – Franz Zeller, Ferdinand Strasser und Johann Hoffmann – am 30. September 1942 im Landesgericht in Wien hingerichtet und Volksgerichtsverfahren gegen 16 weitere Menschen angestrengt.
Im damaligen Gefangenenhaus im Kreisgericht, heute Landesgericht Krems, waren Frauen mit kürzeren Haftstrafen inhaftiert. Die Justizanstalt Stein wiederum war in der NS-Zeit das größte Gefängnis der „Ostmark“. 1945 befanden sich dort rund 1.800 Gefangene aus verschiedenen Nationen. Viele von ihnen waren aus politischen Gründen inhaftiert worden, z.B. aufgrund regimekritischer Äußerungen, des Hörens von Feindsendern, der Verteilung von Flugblättern, des Sammelns von Spenden für inhaftierte Sozialdemokrat:innen und Kommunist:innen oder des bewaffneten Widerstands gegen das NS-Regime. Als die Rote Armee im April 1945 Wien befreit hatte und näher rückte, sollten alle Gefangenen freigelassen werden. Unter dem Vorwand der Niederschlagung einer Revolte fand stattdessen am 6. April 1945 im Gefängnishof ein Massaker an den freigelassenen Gefangenen statt. Zeitgleich suchte die Waffen-SS die Umgebung nach entlassenen Häftlingen ab. Unterstützt wurde sie von Einheiten der lokalen Gendarmerie, Volkssturmtrupps und der Bevölkerung in den umliegenden Ortschaften. Rund 600 Häftlinge wurden so nicht nur im Stadtgebiet von Krems, sondern auch in der weiteren Umgebung, in Hadersdorf am Kamp, Theiß, Hörfarth, Paudorf und an anderen Orten, durch Massenerschießungen ermordet.