Descriptions of ecological networks typically assume that the same interspecific interactions occur each time a community is observed. This contrasts with the known stochasticity of ecological communities: community composition, species abundances and link structure all vary in space and time. Moreover, finite sampling generates variation in the set of interactions actually observed. For interactions that have not been observed, most datasets will not contain enough information for the ecologist to be confident that unobserved interactions truly did not occur. Here, we develop the conceptual and analytical tools needed to capture uncertainty in the estimation of pairwise interactions. To define the problem, we identify the different contributions to the uncertainty of an interaction. We then outline a framework to quantify the uncertainty around each interaction by combining data on observed co-occurrences with prior knowledge. We illustrate this framework using perhaps the most extensively sampled network to date. We found significant uncertainty in estimates for the probability of most pairwise interactions. This uncertainty can, however, be constrained with informative priors. This uncertainty scaled up to summary measures of network structure such as connectance and nestedness. Even with informative priors, we are likely to miss many interactions that may occur rarely or under different local conditions. Overall, we demonstrate the importance of acknowledging the uncertainty inherent in network studies, and the utility of treating interactions as probabilities in pinpointing areas where more study is needed. Most importantly, we stress that networks are best thought of as systems constructed from random variables, the stochastic nature of which must be acknowledged for an accurate representation. Doing so will fundamentally change network analyses and yield greater realism.