In this paper we give a new variation of the prime labeling. We call a graph \(G\) with vertex set \(V(G)\) has an odd prime labeling if its vertices can be labeled distinctly from the set \(\big\{1, 3, 5, ...,2\big|V(G)\big| -1\big\}\) such that for every edge \(xy\) of \(E(G)\) the labels assigned to the vertices of \(x\) and \(y\) are relatively prime. A graph that admits an odd prime labeling is called an <i>odd prime graph</i>. We give some families of odd prime graphs and give some necessary conditions for a graph to be odd prime. Finally, we conjecture that every prime graph is odd prime graph.