We introduce novel optical solitons that consist of a periodic and a spatially localized component coupled nonlinearly via cross-phase modulation. The spatially localized optical field can be treated as a gap soliton supported by the optically induced nonlinear grating. We find different types of these band-gap composite solitons and demonstrate their dynamical stability.