Random packings of stiff rods are self-supporting mechanical structures stabilized by long range interactions induced by contacts. To understand the geometrical and topological complexity of the packings, we first deploy X-ray computerized tomography to unveil the structure of the packing. This allows us to directly visualize the spatial variations in density, orientational order, and the entanglement, a mesoscopic field that we define in terms of a local average crossing number, a measure of the topological complexity of the packing. We find that increasing the aspect ratio of the constituent rods in a packing leads to a proliferation of regions of strong entanglement that eventually percolates through the system, and correlated with a sharp transition in the mechanical stability of the packing. To corroborate our experimental findings, we use numerical simulations of contacting elastic rods, and characterize their stability to static and dynamic loadings. Our experiments and computations lead us to an entanglement phase diagram that we also populate using published experimental data from pneumatically tangled filaments, worm blobs, and bird nests, along with additional numerical simulations using these datasets. Together, these show the regimes associated with mechanically stable entanglement as a function of the statistics of the packings and loading, with lessons for a range of systems from reconfigurable architectures and textiles to active morphable filamentous assemblies.