Spam is a problem that refuses to go away. An immense amount of time and money is currently devoted to hiding spam, but not enough is devoted to effectively preventing it. CAPTCHAs are a prevalent spam prevention mechanism, but are getting harder for humans to solve and easier for programs to "break". CAPTCHAs also cannot prevent spam from hijacked accounts since they are mostly used during account creation. Proof-of-work approaches are gaining popularity, but current implementations are not effective enough and cannot be used by generic web applications. We present MetaCAPTCHA, an application-agnostic spam prevention service for web applications. MetaCAPTCHA dynamically issues CAPTCHAs and proof-of-work "puzzles" while ensuring that more malicious users solve "harder" puzzles. In order to support its operation, MetaCAPTCHA implements a novel secure protocol -- for authenticating web sites and validating proof-of-work solutions -- that allows for seamless integration across a variety of web applications.