Der 1926 eingeführte Artikel 58 des Strafgesetzbuches („Vaterlandsverrat“) betraf „konterrevolutionäre Verbrechen gegen den Staat“. Der ursprünglich den „Vaterlandsverrat“ betreffende Paragraf 1 wurde 1934 um folgende vier Punkte ergänzt:
a) Handlungen von Sowjetbürgern zum Nachteil der militärischen Leistungsfähigkeit der UdSSR, der staatlichen Unabhängigkeit oder der Unantastbarkeit des Territoriums wie Spionage, Verrat eines militärischen oder eines Staatsgeheimnisses, Überlaufen zum Feind oder Flucht ins Ausland;
b) gleiche Verbrechen begangen durch Militärangehörige;
c) Verantwortlichkeit von Familienmitgliedern der „Verräter“, selbst wenn sie nichts über die Vorbereitung oder die Durchführung eines Verrates gewusst hattenf; und
d) die Verantwortlichkeit bei der Nichtanzeige eines geplanten oder begangenen Verrates.
Für die Punkte a) und b) war als Höchststrafe „Todesstrafe und Konfiskation des Vermögens“ vorgesehen. Eine Strafminderung zu zehn Jahren Freiheitsentzug ermöglichte nur Punkt a) bei Vorliegen mildernder Umstände.
Anklagen wegen „Vaterlandsverrates“ wurden im Stalinismus zur physischen Liquidierung tatsächlicher oder vermeintlicher politischer Gegner des sowjetischen Regimes genutzt. Während und nach dem Zweiten Weltkrieg wurden auf Grundlage dieses Vorwurfs massenhaft Militärangehörige, die in Kriegsgefangenschaft geraten waren sowie zur Zwangsarbeit ins Ausland deportierte Zivilisten angeklagt. Die Beteiligung am nationalen Widerstand gegen das Regime wurde – wie in den baltischen Staaten oder der Ukraine – ebenfalls als „Verrat“ gewertet.
Die Liberalisierung der Strafverfolgungspolitik nach Stalins Tod führte zu einer drastischen Verringerung der Verurteilungen. Im Gesetz der UdSSR vom 25. Dezember 1958 „Über die strafrechtliche Verantwortlichkeit bei Verbrechen gegen den Staat“ (Artikel 1) wurde das Kriterium des Vorsatzes eingeführt. So wurden beispielsweise der „Beistand zugunsten eines fremden Staates bei der Durchführung feindlicher Tätigkeiten gegen die UdSSR“ sowie „Verschwörungen mit dem Ziel der Machtergreifung“ dem Artikel hinzugefügt. Diese Spezifikationen waren vormals in anderen Paragrafen des Artikels 58 geregelt worden. Zwar wurden nach wie vor strenge Strafen einschließlich der Todesstrafe angedroht, der Artikel wurde jedoch selbst in Zeiten politischer Krisen in der UdSSR nur selektiv angewendet. 1961 wurde Artikel 58 durch Artikel 64 Strafgesetzbuch der RSFSR ersetzt.