Quantifying the complexity of ecological networks has remained an elusive task. Primarily, the definition of the complexity of the system has been built on the basis of its structure or behaviour. These definitions ignore the notion of the ‘physical complexity’ of the system, which can measure the amount of information contained in an ecological network, and the difficulty associated with compressing it. We present the use of relative rank deficiency and SVD entropy as measures of the ‘external’ and ‘internal’ complexity of ecological networks respectively. Using bipartite ecological networks, we find that they all show a very high, almost maximal, physical complexity and that pollination networks, in particular, are more complex when compared to other types of interaction networks. In addition, we find that SVD entropy relates to other structural measures of complexity (nestedness, connectance, and spectral radius), but does not inform about the resilience of a network when simulating extinction cascades, which has previously been reported for structural measures of complexity. Further exploration on the complexity of networks reveals that connectance constrains complexity and that ecological networks may be less complex than expected when compared to random networks. We argue that SVD entropy provides a fundamentally more ‘correct’ measure of network complexity and should be added to the toolkit of descriptors for ecological networks moving forward as well as some insights on the complexity of networks.