Accumulated proof-of-work approaches for protecting network resources against denial-of-service attacks are disclosed. A client computer or other requester is required to perform work, such as repeatedly hashing a message until a specified number of bits is zero, as a condition for accessing a resource. Proof of the work performed by a legitimate requester is accumulated across multiple requests, so that established users of a resource are not penalized when proof-of-work is used to prevent a denial of service attack. Requesters who cannot show accumulated work greater than a specified threshold are required to perform additional work. In certain embodiments, work may be accumulated only within a specified time window, and the threshold may vary according to resource capacity or loading. Proof-of-work values may be communicated between the user and the resource in cookies.