A system and method for providing message-based leasing of resources in a distributed computing environment. Services may issue leases to clients and provide operations on those leases. The lease functionality of a service may be defined in an XML message schema. Gates may be used to perform lease operations. Leases may be granted for a period that may be negotiated. Leasing messages for performing leasing operations may be defined. An automatic lease renewal mechanism may be implemented to relieve the client of the responsibility of handling lease renewal messages. In one embodiment, of an automatic lease renewal mechanism, each gate may receive renewal messages and automatically respond to them without help from the client process. In another embodiment, a client gate may monitor elapsed time and send a lease renewal message prior to the expiration of a current lease period. In one embodiment, the renewal request may claim the lease at a current access level or at a different access level. In one embodiment, a message gate may contain a single, set-aside renewal response message that is automatically sent to the service when the gate receives the renewal message. In one embodiment using time-based leasing, a lease renewal request from a client to a service may specify a requested lease period, and the service leasing the resource to the client may grant a lease period equal to or less than the specified period.