Phages shape the structure of natural bacterial communities and can be effective therapeutic agents. Bacterial resistance to phage infection, however, limits the usefulness of phage therapies and could destabilise community structures, especially if individual resistance mutations provide cross-resistance against multiple phages. We currently understand very little about the evolution of cross-resistance in bacteria-phage interactions. Here we show that the network structure of cross-resistance among spontaneous resistance mutants of Pseudomonas aeruginosa evolved against each of 27 phages is highly modular. The cross-resistance network contained both symmetric (reciprocal) and asymmetric (nonreciprocal) cross-resistance, forming two cross-resistance modules defined by high within- but low between-module cross-resistance. Mutations conferring cross-resistance within modules targeted either lipopolysaccharide or type IV pilus biosynthesis, suggesting that the modularity of cross-resistance was structured by distinct phage receptors. In contrast, between-module cross-resistance was provided by mutations affecting the alternative sigma factor, RpoN, which controls many lifestyle-associated functions, including motility, biofilm formation, and quorum sensing. Broader cross-resistance range was not associated with higher fitness costs or weaker resistance against the focal phage used to select resistance. However, mutations in rpoN, providing between-module cross-resistance, were associated with higher fitness costs than mutations associated with within-module cross-resistance, i.e., in genes encoding either lipopolysaccharide or type IV pilus biosynthesis. The observed structure of cross-resistance predicted both the frequency of resistance mutations and the ability of phage combinations to suppress bacterial growth. These findings suggest that the evolution of cross-resistance is common, is likely to play an important role in the dynamic structure of bacteria-phage communities, and could inform the design principles for phage therapy treatments.