The more politically conservative Americans are, the more restrictive their sexual attitudes are. A natural follow-up question is how this difference in attitudes relates to actual behavior. But self-reports of sexual behavior may be compromised by a social desirability bias that is influenced by the very sexual attitudes at issue. We employed a non-self-reported measure of sexual behavior: usage of the adultery-focused dating website Ashley Madison. Linking an August 2015 leak of user data from Ashley Madison to 2012 voter registration rolls from five U.S. states, we found 80,000 matches between 200,000 Ashley Madison user accounts and 50 million voters. According to simple rates in the sample, and also to predictively validated regression models controlling for state, gender, and age, we found that Democrats were least likely to use Ashley Madison, Libertarians were most likely, and Republicans, Greens, and unaffiliated voters were in between. Our results provide support for theories arguing that people with stricter sexual attitudes are paradoxically more likely to engage in deviant sexual behavior.