Plným názvem Geheime Staatspolizei (Tajná státní policie), byla založena roku 1933 v Prusku Hermannem Göring (v té době Pruským ministrem vnitra) jako speciální policejní neuniformovaná složka určená k potírání politické protistátní činnosti.
Vznikla sloučením několika nezávislých policejních odborů. V roce 1934 se v důsledku mocenských tahanic dostala do područí SS a její působnost je rozšířena mimo Prusko do celého Německa. Je personálně obsazována příslušníky SS a začíná srůstat s organizací SD (Sicherheitdienst - Bezpečnostní služba - rozvědka a kontrarozvědka SS).
Trend srůstání policejních složek s SS dále pokračoval v roce 1936, kdy se Heinrich Himmler stal šéfem policie a fakticky zahrnul kriminální policii (Kripo) do struktur SS. Tento trend dále pokračuje za Reinharda Heydricha, kdy v roce 1939 je Gestapo a další bezpečnostní a zpravodajské složky s výjimkou armádní zpravodajské služby - Abwehru, včleněno do struktur Říšského hlavního úřadu bezpečnosti (RSHA) a dále v rámci něho prorůstá s Kripem do instituce bezpečnostní policie - Sicherheits Polizei (Sipo).
Vnitřní struktura Gestapa v roce 1939
Amt A (Odbor A) - Politická opozice
A1 - Komunisté a socialisté (tj. sociální demokraté)
A2 - Protisabotáž
A3 - Reakcionáři, liberálové (a nespecifická opozice)
A4 - Atentátníci
Amt B (Odbor B) - Sekty a církve
Amt C (Odbor C) - Administrativní sekce a záležitosti strany
Amt D (Odbor D) - Správa okupovaných území
D1 - Protektorátní území - Protektorát Böhmen und Mähren, Jugoslávie, Řecko
D2 - Generální guvernement
D3 - Emigranti a cizinci nepřátelského smýšlení (pro oblast říše)
D4 - Okupovaná území (západní) - Francie, Belgie, Holandsko, Dánsko
D5 - Okupovaná východní teritoria
Amt E (Odbor E) - Kontrašpionáž a vnitřní bezpečnost
E1 - Říše
E2 - Politické formace
E3 - Západ
E4 - Skandinávie (Sever)
E5 - Východ
E6 - Jih
Amt F (Odbor F) - Hraniční a pohraniční policie
Pozn: Podřazená struktura např A4, E6 a pod je označována jako Referat.
Amt I (I. Odbor) – vedení místní úřadovny (organizační, správní, osobní)
Amt II (II. Odbor) – hospodářské a správní záležitosti
Amt III (III. Odbor) – skupina pro zvláštní úkoly (později převedena pod odd. IV, referát 3)
Amt IV (IV. Odbor) – exekutiva (příjem zatčených, příjem hlášení od konfidentů a důvěrníků, formace pro boj s odbojovým hnutím, provádění prohlídek, intervence v případech sabotáže a vloupání politického charakteru, ale i archiv úřadovny – zabavené tiskoviny, letáky atd.):
IV-1a – komunisté a sociální demokraté
IV-1b – pravicový odboj
IV-1c – váleční zajatci a nuceně nasazení
IV-2a – sabotáže, nepovolené držení zbraní
IV-2b – protipartyzánský a protiparašutistický odbor
IV-3 – kontrašpionáž (původně samostatný Odbor III, zrušen a restrukturalizován 1938)
IV-4 – židé, spolky, církve
IV-5 – ochranná vazba
IV-6a – kartotéka a spisovna
IV-N – agenda konfidentů
Amt V (V. Odbor) – Kriminální policie (Kripo), (včlenění do struktury od poloviny roku 1944)
Pozn: Podřazená struktura např II-C, IV-2 a pod je označována jako Referat. Reálně jako samostatná kancelář na místní úřadovně existuje pouze Leitstelle tj. Amt I, ostatní Odbory jsou formální správní jednotky a jednotlivé kanceláře a struktury jsou již přímo vlastní referáty.