When was visible light for the first time created? "A few minutes into the expansion, when the temperature was about a billion (one thousand million) kelvin and the density was about that of air, neutrons combined with protons to form the universe's deuterium and helium nuclei in a process called Big Bang nucleosynthesis. Most protons remained uncombined as hydrogen nuclei. As the universe cooled, the rest mass energy density of matter came to gravitationally dominate that of the photon radiation. 

After about 379,000 years the electrons and nuclei combined into atoms (mostly hydrogen); hence the radiation decoupled from matter and continued through space largely unimpeded. This relic radiation is known as the cosmic microwave background radiation."

The question now is, when you count back starting with the cosmic background radiation which is now in far red (2,7K) at what time was there for the first time visible light, or was is right after the creation of atoms about 379,000 after the big bang?
The best model we have is that of electro-weak unification. 

The photon is an quantum of the electromagnetic field, and as long as there has been an electromagnetic field, excitation of the field have existed.

The "weak" nuclear interaction is another field, (it has the effect of changing up quarks to down quarks, and so is responsible for beta decay of radioactive material). Quanta of the weak field are rather different from photons. They are charged and have mass, but at very high energies (a million billion degrees or so) the electromagnetic and weak fields are unified into a single "electroweak" interaction.

But after the universe had cooled (it took sometime between $10^{-36}$ and $10^{-32}$ seconds) the weak and electromagnetic fields split, and the first true photons formed.

These photons didn't get very far before colliding with other particles that were being formed. As you note, it took nearly 400000 years until the universe cooled enough to become transparent.

Now you mention visible light. The photons formed after the split would have had very high energies, we would call most of them gamma rays if they existed today. But as photon of all energies could be formed, a small fraction would have been in the visible range.

At recombination, when the universe became transparent, the temperature was about 3000K, at which temperature most photons are in the infra red range, but enough are visible to have given the universe a very bright orange-red colour, similar to the colour of a lightbulb.