A total prime labeling of a graph is an extension of a prime labeling in which we distinctly label the vertices and edges with the integers $1, 2, \ldots, \lvert V \rvert + \lvert E \rvert$. In a total prime labeling, the labels on adjacent vertices are relatively prime, and for each vertex of degree at least 2, the greatest common divisor of the labels on its incident edges is 1. In addition to introducing total prime labelings for various classes of graphs, this talk will highlight certain classes of graphs that do not allow a total prime labeling.