A new chromatic parameter of graphs, the Hamiltonian chromatic number, is introduced in this paper. For vertices \(u\) and \(v\) in a connected graph \(G\) of order \(n\), the length of a longest \(u\)-\(v\) path in \(G\) is denoted by \(D(u,v)\). A Hamiltonian coloring \(c\) of \(G\) is an assignment \(c\) of colors (positive integers) to the vertices of \(G\) such that \(D(u,v)+| c(u)-c(v)| \geq n-1\) for every two distinct vertices \(u\) and \(v\) of \(G\). The value \(\text{hc}(c)\) of a Hamiltonian coloring \(c\) of \(G\) is the maximum color assigned to a vertex of \(G\). The Hamiltonian chromatic number \(\text{hc}(G)\) of \(G\) is \(\min\{\text{hc}(c)\}\) over all Hamiltonian colorings \(c\) of \(G\). This parameter is determined for complete graphs \(K_n\), the complete bipartite graphs \(K_{r,s}\) and for the cycle \(C_n\) as follows: \(\text{hc}(K_n)=1\), \(\text{hc}(K_{1,n-1})=(n-2)^2+1\) for \(n\geq2\), \(\text{hc}(K_{r,r})=r\) for \(r\geq2\), \(\text{hc}(K_{r,1})= (s-1)^2+(r-1)^2\) for \(2\leq r