We present what is to our knowledge the first dual-band negative index metamaterial that operates in the visible spectrum. The optimized four-functional-layer metamaterial structure exhibits the first double-negative (i.e., simultaneously negative permittivity and permeability) band in the red region of the visible spectrum with a figure of merit of 1.7 and the second double-negative band in the green region of the visible spectrum with a figure of merit of 3.2. The optical behavior of the proposed structure is independent of the polarization of the incident field. This low-loss metamaterial structure can be treated as a modified version of a fishnet metamaterial structure with an additional metal layer of different thickness in a single functional layer. The additional metal layer extends the diluted plasma frequency deep into the visible spectrum above the second-order magnetic resonance of the structure and hence provides a dual-band operation with simultaneously negative effective permittivity and permeability. Broadband metamaterials with multiple negative index bands may be possible with the same technique by employing higher-order magnetic resonances. The structure can be fabricated with standard microfabrication techniques that have been used to fabricate fishnet metamaterial structures.