A network-based discovery system and service are disclosed that provide client discovery services to a number of clients over a network. The network-based discovery system includes a database that stores discovery information of client network-based resource configurations. The discovery information may be obtained from client resources by client-side discovery components that are placed on client resources, obtain the discovery information and that send the information to the discovery system. The discovery system analyzes the discovery information to determine the client network-based resource configurations and generates client network-based resource configuration representations for the respective clients. The client network-based resource configuration representation may include a description of, and dependencies among, a plurality of computer-based resources. The discovery service may operate across a client network that spans both of a client's enterprise data networks as well as resources that are operated on behalf of the same client by a service provider network.