After the dissolution of the Soviet Union, he worked as the head, political secretary and deputy chairman of the Regional Department of the Citizens' Union's Youth Branch from 1993-1995, serving as the organization's press secretary from 1994 to 1995.

A year later, Tkeshelashvili graduated from Tbilisi State University with a degree in Law.

In 1999, he was re-elected to the parliament, working as chairman of the Subcommittee for Relations with Media and Non-governmental Organizations of the Human Rights Committee from 1999 through 2003.

The following year, he won Edmund S. Muskie scholarship, subsequently obtaining LLM from Emory University in 2006.

As the minister, he was able to sign park partnership agreements with the US government which ensured financial and technical assistance to Georgia and the establishment of a sister-park relationship between Point Reyes and Kolkheti National Park.