Tolentino was first appointed to the post of OIC Mayor of Tagaytay from 1986 to 1987 by former President Corazon Aquino. He ran unopposed in the 1995 general election for Mayor of Tagaytay and served for nine years from 1995 to 2004. Under his administration, he created the Tagaytay Office of Public Safety, which later became the basis of policies he put into force as chair of the MMDA. He also initialized the Character First programs which encourages governments, government leaders, civic organizations and religious organizations to band together to establish a "city" or "community" of character with character traits of a Filipino every month.
On July 27, 2010, Tolentino was appointed by President Benigno Aquino III as the ninth chairman of the Metropolitan Manila Development Authority. He is the first and only non-resident of Metro Manila to be appointed to the post. On August 2013, Tolentino, as MMDA chairman, launched the first Metro Manila Integrated Bus Terminal known as the Southwest Integrated Provincial Transport Terminal. On September 19, 2013, Tolentino signed the Metro Manila Outdoor Media Magna Carta along with various advertising groups, setting the terms for regulating outdoor advertisements in Metro Manila. Among the terms in the 15-page agreement were a 216-square meter limitation on all outdoor signs and structures, with 30 percent of the space of ground level ads allotted "for landscape works or vertical gardens". Prior to the signing of the document, no limit had been placed on the size of advertisements, such that a number of billboards as big as 1,000 square meters had been allowed. The document provided a nine-month grace period for advertisers to be able to comply. To address the traffic situation in Metro Manila and to offer transportation alternative to the public, Tolentino relaunched the Pasig River Ferry System last April 2014, in coordination with the Pasig River Rehabilitation Commission and the Department of Transportation and Communications. As chair of the MMDA, Tolentino was also designated by Metro Manila Commission Executive Order No. 86-09 as chair of the annual Metro Manila Film Festival, in which capacity Tolentino introduced a number of changes, including the introduction of new contest categories and the removal of box office receipts from the criteria for the selection of best picture starting from the 2010 edition.
2016 Campaign
Tolentino was originally included as a senate candidate in the LP-endorsed Daang Matuwid Koalisyon. However, things did not turn out well with the party. This eventually led to his independent candidacy and placed 13th.
