A widespread theory in the province of Papua, Eastern Indonesia, links the spread of sex workers and HIV/AIDS to a broader government conspiracy to eliminate indigenous Papuans. Explicit conspiratorial thinking by indigenous Papuans draws from diverse evidence such as provincial partition legislation, patterns of sex-industry usage, economic transformations, rumors of witchcraft, and new automobile technology. This article argues against treating conspiracy theories about AIDS simply as symbolically powerful rumors expressing indigenous Papuans' perceptions of oppression and unequal access to state resources. Rather, conspiracy theories articulate awareness of inconsistencies in the government's formulation and administration of sexual regulations and AIDS-prevention policies. AIDS conspiracy theories can therefore be understood as pragmatic and detailed interpretations of Papuan lived experiences in a context of ethnically disenfranchising forms of power in post-Suharto Indonesia.