Energy of a fission nuclear bomb comes from the gravitational energy of the stars.
Protons and neutrons can coalesce into different kinds of bound states. We call these states atomic nuclei. The ones with the same number of protons are called isotopes, the ones with different number are nuclei of atoms of different kinds.
There are many possible different stable states (that is, stable nuclei), with different number of nucleons and different binding energies. However there are also some general tendencies for the specific binding energy per one nucleon (proton or neutron) in the nuclei. States of simple nuclei (like hidrogen or helium) have the lowest specific nucleon binding energy amongst all elements, but the higher is the atomic number, the higher the specific energy gets. However, for the very heavy nuclei the specific binding energy starts to drop again.
Here is a graph that sums it up:
http://en.wikipedia.org/wiki/File:Binding_energy_curve_-_common_isotopes.svg
It means that when nucleons are in the medium-atomic number nuclei, they have the highest possible binding energy. When they sit in very light elements (hidrogen) or very heavy ones (uranium), they have weaker binding. Thus, one can say that for the low "every-day" temperatures, the very heavy elements (like the very light ones) are quasistable in a sense.
Fission bomb effectively "lets" the very heavy atomic nuclei (plutonium, or uranium) to resettle to the atoms with lower number of nucleons, that is, with higher bound energies. The released binding energy difference makes the notorious effect. In terms of the graph cited above, it corresponds to nucleons moving from the right end closer to the peak.
Yet this is not the only way to let nucleons switch to the higher binding energy state than the initial one. We can "resettle" very light elements (like hydrogen) and let nucleons move to the peak from the left. That would be fusion.
Heavy nucleons emerge in the stars. Here the gravitational energy is high enough to let the nucleons "unite" into whatever nuclei they like. Stars usually are formed from the very light elements and the nucleons inside, again, tend to get to the states with lower energies, and form more "medium-number" nuclei. The energy difference powers stars and we see the light emission, high temperatures and all other fun effects.
However, sometimes the temperatures in the stars are so high, that nucleons form the very heavy nuclei from the medium-number nuclei. even though there is no immediate "energy" benefit.
These heavy elements then disseminate everywhere with the death of the star. This stored star energy can then be released in the fission bomb.
Best Answer
Have you ever wondered why do the protons and neutrons stay together in the first place?
These particles are bound to the nucleus by attracting forces (strong nuclear forces) which I won't dwell into in this answer rather I shall speak in terms of energy. There exists energy of interaction, called binding energy, which keeps the nucleons together.
The nucleus as a whole has a lower potential energy than their individual particles held separately which implies that you need to supply energy to disintegrate the nucleus (which is why a moving particle, usually neutrons, are bombarded with the fission reactant to initiate a non-spontaneous nuclear reaction; the moving particle has kinetic energy). Notice that the nucleus is lighter than its constituent elements. As you said, energy and mass are interconvertible. The missing mass takes the form of binding energy (assuming that other forms of energy of the nucleus and the constituents are zero).
The mechanism of a non-spontaneous nuclear fission reaction can be described in very simple manner as follows.
Moving particle bombards the fission reactant's nucleus and transfers the energy to the nucleus. The nucleus begins to waggle and at one point (unless the newly formed nucleus with the bombarding particle is stable) it breaks apart into two or more pieces.
The new products have different binding energy. This difference in binding energy is the energy which is released from the reaction (in the form of kinetic energy of the products).
The above mechanism is highly simplified and lot of complicating factors have been ignored from the above mechanism.