Techniques for policy-based connection provisioning using Domain Name System (DNS) requests are described herein. The techniques may include receiving policy data associated with one or more headend nodes that manage connections to computing resources. Additionally, the techniques may include receiving a DNS request from a client device to establish a connection between the client device and a first headend node of the one or more headend nodes. The DNS request may include an attribute associated with the client device. A provisioning service may determine that the connection should be established between the client device and the first headend node based at least in part on evaluating the attribute with respect to the policy data. Additionally, the techniques may include sending an internet protocol (IP) address, which is associated with the first headend node, to the client device to facilitate establishment of the connection.