We investigate the effects of an external magnetic field in the gap structure of a color superconductor with three massless quark flavors. Using an effective theory with four-fermion interactions, inspired by one-gluon exchange, we show that the long-range component B of the external magnetic field that penetrates the color-flavor locked phase modifies its gap structure, producing a new phase of lower symmetry. A main outcome of our study is that the B field tends to strengthen the gaps formed by Q-charged and Q-neutral quarks that coupled among themselves through tree-level vertices. These gaps are enhanced by the field-dependent density of states of the Q-charged quarks on the Fermi surface. Our considerations are relevant for the study of highly magnetized compact stars.