The origin of the chemical elements that make up our world is one of the oldest most fundamental scientific questions. The universe after the Big Bang consisted only of hydrogen and helium with traces of lithium. All the other elements, including the carbon in our bodies, the iron, silicon, and oxygen that makes up most of our earth, have been created later by nuclear reactions in stars. However, the origin of many elements beyond iron, including gold and uranium, is still a mystery. These elements are attributed to a process called the r-process (rapid neutron capture process) which is of fundamental importance in explaining the origin of stable nuclei and isotopes beyond the iron group (A>90-100). The site of the r process is not known but supernova explosions and/or colliding neutron stars are prime suspects. The problem is that none of the models (related to these sites) can produce r-process elements in the correct proportions as we find them, for example, in the solar system or in certain very old stars. I will discuss an exciting alternative related to quark stars, a new class of compact stars that contain matter at the highest densities. Proposed observational features of quark stars, the probability of their detection, as well as some interesting connections to r-process nucleosynthesis will be presented. I will focus on an alternative based on a dynamical picture of decompressing neutron matter from the surface of quark stars in the scenario termed the Quark-Nova, which is particularly effective for producing the r-process pattern of heavy elements.