Background: Molecular interactions need to be taken into account to adequately model the complex behavior of biological systems. These interactions are captured by various types of biological networks, such as metabolic, gene-regulatory, signal transduction and protein-protein interaction networks. We recently developed Natalie, which computes high-quality network alignments via advanced methods from combinatorial optimization.Results: Here, we present NatalieQ, a web server for topology-based alignment of a specified query protein-protein interaction network to a selected target network using the Natalie algorithm. By incorporating similarity at both the sequence and the network level, we compute alignments that allow for the transfer of functional annotation as well as for the prediction of missing interactions. We illustrate the capabilities of NatalieQ with a biological case study involving the Wnt signaling pathway.Conclusions: We show that topology-based network alignment can produce results complementary to those obtained by using sequence similarity alone. We also demonstrate that NatalieQ is able to predict putative interactions. The server is available at: http://www.ibi.vu.nl/programs/natalieq/. © 2014 El-Kebir et al.; licensee BioMed Central Ltd.