Invadopodia are subcellular organelles thought to be critical for extracellular matrix (ECM) degradation and the movement of cells through tissues. Here we examine invadopodia generation, turnover, and function in relation to two structural aspects of the ECM substrates they degrade: cross-linking and fiber density. We set up a cellular automaton computational model that simulates ECM penetration and degradation by invadopodia. Experiments with denatured collagen (gelatin) were used to calibrate the model and demonstrate the inhibitory effect of ECM cross-linking on invadopodia degradation and penetration. Incorporation of dynamic invadopodia behavior into the model amplified the effect of cross-linking on ECM degradation, and was used to model feedback from the ECM. When the model was parameterized with spatial fibrillar dimensions that closely matched the organization, in real life, of native ECM collagen into triple-helical monomers, microfibrils, and macrofibrils, little or no inhibition of invadopodia penetration was observed in simulations of sparse collagen gels, no matter how high the degree of cross-linking. Experimental validation, using live-cell imaging of invadopodia in cells plated on cross-linked gelatin, was consistent with simulations in which ECM cross-linking led to higher rates of both invadopodia retraction and formation. Analyses of invadopodia function from cells plated on cross-linked gelatin and collagen gels under standard concentrations were consistent with simulation results in which sparse collagen gels provided a weak barrier to invadopodia. These results suggest that the organization of collagen, as it may occur in stroma or in vitro collagen gels, forms gaps large enough so as to have little impact on invadopodia penetration/degradation. By contrast, dense ECM, such as gelatin or possibly basement membranes, is an effective obstacle to invadopodia penetration and degradation, particularly when cross-linked. These results provide a novel framework for further studies on ECM structure and modifications that affect invadopodia and tissue invasion by cells.