Examples provide for automatically provisioning hosts in a cloud environment. A cloud daemon generates a cloud host-state configuration, for a given cloud instance of a host, stored on a cloud metadata service prior to first boot of the given cloud instance of the host. A first boot of a plurality of cloud instances of hosts is performed using a stateless, master boot image lacking host-specific configuration data. On completion of the first boot of a given cloud instance of a host, the cloud host-state configuration is installed on the master boot image to generate a self-configured boot image including host-specific configuration data for the given cloud instance of the host. A second boot is performed on the given cloud instance of the host by executing the self-configured boot image to automatically provision the given cloud instance of the host in the cloud environment.