Apical-basal polarity is a hallmark of epithelia and needs to be remodeled when epithelial cells undergo morphogenetic cell movements. Here, we analyze border cells in the Drosophila ovary to address how apical-basal polarity is remodeled and turned into front-back and inside-outside as well as apical-basal polarities, during collective migration. We find that the Crumbs (Crb) complex is required for the generation of the three distinct but interconnected cell polarities of border cells. Specifically, the Crb complex, together with the Par complex and the endocytic recycling machinery, ensures the strict distribution of two distinct populations of aPKC at the inside apical junction and near the outside lateral membrane. Interestingly, aPKC distributed near the outside lateral membrane interacts with Sif and promotes Rac-induced protrusions, whereas alteration of the aPKC distribution pattern changes the pattern of protrusion formation, leading to disruption of all three polarities. Therefore, we demonstrate that aPKC, spatially controlled by the Crb complex, is a key polarity molecule coordinating the generation of three distinct but interconnected cell polarities during collective migration.