The matching function, the central building block of models with search frictions, remains largely a “black box.” In this paper, we use tools from network theory to unpack it showing how the structure of the underlying connections between applicants and firms determines the emergent matching function’s properties. Our overarching message is that structure counts. We show that for complex structures, captured by non-random graphs, the matching function depends on whole sets of connections rather than just the sizes of the two sides of the market. For simpler, random graph structures, the matching function depends only on the sizes of the two sides and a few structural parameters, as typically assumed in the literature. Structures characterized by greater asymmetries in the connections of applicants reduce the matching function’s overall match efficacy, while more connections across applicants can have ambiguous effects on it. In the special case when the underlying connections are given by an Erdös-Rényi network, we illustrate that the way applicants’ links vary with the sizes of the two sides of the market plays a critical role for the matching function to exhibit constant returns to scale, or even to be of specific functional forms, like Cobb-Douglas or CES.