Methods and apparatus for efficient monitoring of network fleets are described. A list of network addresses of a set of hosts at which resources are to be monitored from a monitoring server of a provider network may be received at the monitoring server. The monitoring server may initiate establishment of a persistent network connection to a monitoring agent installed at a monitored host. A plurality of health messages from the monitoring agent may be obtained via the connection, including a host status entry for the monitored host and a resource status entry for at least one resource configured at the monitored host. A representation of the health messages may be saved in a repository for analysis.