Systems and methods are provided for federated search. Search results can be federated across cloud-based data stores having data accessible to applications hosted in the cloud and private data stores protected by a data security provider that manages communications between a private network and the cloud. A search query invoked by a client of a cloud-based application can be partitioned into search criteria applicable to the cloud-based data stores and search criteria applicable to the private data store. The cloud-based application can perform a search using the search criteria applicable to the cloud-based data stores and use results of a search against the private data store to federate the results.