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. The leasing messages may include messages to renew a lease and to cancel a lease. Leasing messages may include embedded credentials for authenticating the sender of the message. A client may embed a credential in messages sent to the service. The service may then authenticate the credential when received in a message from the client. The issuing and embedding of credentials in leasing messages may be used to provide a secure leasing environment, effectively prohibiting anyone but an authorized, credentialed client (and the service issuing the lease) from performing functions on the lease.