An efficient multimode quantum memory is a crucial resource for long-distance quantum communication based on quantum repeaters. We propose a quantum memory based on spectral shaping of an inhomogeneously broadened optical transition into an atomic frequency comb (AFC). The spectral width of the AFC allows efficient storage of multiple temporal modes without the need to increase the absorption depth of the storage material, in contrast to previously known quantum memories. Efficient readout is possible thanks to rephasing of the atomic dipoles due to the AFC structure. Long-time storage and on-demand readout is achieved by use of spin states in a lambda-type configuration. We show that an AFC quantum memory realized in solids doped with rare-earth-metal ions could store hundreds of modes or more with close to unit efficiency, for material parameters achievable today.