In the deconfined phase of quark-gluon plasma, it seems that most of the quarks, antiquarks and gluons should be effectively free in the absence of the linear confining potential. However, the remaining Coulomb-type potential between quarks in the plasma could still be sufficiently strong that certain bound states, notably of heavy quarks such as J/ψ are stable even in the deconfined plasma up to a certain temperature. Baryons can also exist in the deconfined phase provided that the density is sufficiently large. We study three kinds of exotic multi-quark bound states in the deconfined phase of quark-gluon plasma from gravity dual models in addition to the normal baryon. They are k-baryon,(N+ bar k)-baryon and a bound state of j mesons which we call``j-mesonance''. Binding energies and screening lengths of these exotic states are studied and are found to have similar properties to those of mesons and baryons at the leading order. Phase diagram for the exotic nuclear phases is subsequently studied in the Sakai-Sugimoto model. Even though the exotics are less stable than normal baryons, in the region of high chemical potential and low temperature, they are more stable thermodynamically than the vacuum and chiral-symmetric quark-gluon plasma phases (χS-QGP).