This paper presents a client bootstrapping protocol for proxy-based moving target defense system for the cloud. The protocol establishes the identity of prospective clients who intend to connect to web services behind obscure proxy servers in a cloud-based network. In client bootstrapping, a set of initial line of defense services receive new client requests, execute an algorithm to assign them to a proxy server, and reply back with the address of the chosen proxy server. The bootstrapping protocol only reveals one proxy address to each client, maintaining the obscurity of the addresses for other proxy servers. Hiding the addresses of proxy servers aims to lower the likelihood that a proxy server becomes the victim of a denial-of-service (DoS) attack. Existing works address this problem by requiring the solution of computationally intensive puzzles from prospective clients. This solution slows the progression of attacks as well as new clients. This paper presents an alternative idea by observing that limited capacity of handling initial network requests is the primary cause of denial-of-service attacks. Thus, the suggested alternative is to utilize cost-effective high-capacity networks to handle client bootstrapping, thus thwarting attacks on the initial line of defense. The prototype implementation of the protocol using Google’s firebase demonstrates the proof of concept for web services that receive network requests from clients on mobile devices.