Koh resultó elegido ministro principal de Penang en las elecciones estatales de 1990. Aunque el Barisan Nasional, que gobernaba desde 1969 con Lim Chong Eu como jefe de Gobierno, ganó las elecciones, Lim fue derrotado en su circunscripción y se vio constitucionalmente impedido para seguir ejerciendo, por lo que Koh fue seleccionado para ocupar su lugar. Fue consecutivamente reelegido en 1995, 1999 y 2004, en las tres ocasiones por arrolladores márgenes. Durante su mandato, sin embargo, se produjo un considerable aumento de la corrupción, el desempleo y un retroceso económico creciente, a lo que se sumó un constante abandono de Penang de parte del gobierno federal. Durante su último mandato, comenzaron a desatarse protestas contra la mala administración de Penang, considerado previamente como uno de los estados más ricos de Malasia.[1][2][3][4]
Para las elecciones estatales de 2008, Koh decidió no presentarse a la reelección, prefiriendo disputar un escaño en el Dewan Rakyat en las elecciones federales con el objetivo de recibir un puesto en el gabinete de Abdullah Ahmad Badawi. Su decisión provocó un conflicto interno dentro de la seccional penanguita del Barisan Nasional con respecto a quién sería su sucesor. Esto, sumado a la desfavorable situación económica y social de Penang, minó severamente la popularidad de su partido, y en ese contexto, la coalición opositora Pakatan Rakyat (Pacto Popular), liderada en Penang por Lim Guan Eng, obtuvo una resonante victoria, tomando el control del estado y dejando al Gerakan en la irrelevancia política al perder toda su representación en la Asamblea Estatal, luego de haber gobernado durante casi cuarenta años. El propio Koh resultó derrotado en la contienda parlamentaria y, en consecuencia, no pudo acceder al gabinete.[5][6]
Sin embargo, en abril de 2009, fue designado Senador por Penang en el Dewan Negara, siendo además nombrado ministro del Departamento del primer ministro por el nuevo primer ministro Najib Razak. Dimitió como líder del BN de Penang ante su baja popularidad y, tras la debacle masiva del Gerakan en 2013, como presidente del partido a nivel nacional.[7]
