La actual ciudad está construida inmediatamente al norte de una antigua fortificación del principado de Pereyáslav, cuyo origen se remonta al siglo X. La fortaleza original acabó siendo destruida en torno a 1240 en la invasión mongola de la Rus de Kiev. La localidad fue refundada a principios del siglo XIX, como un jútir en el que se asentaron colonos procedentes de Shcherbakivka. A lo largo del siglo, el jútir acabó formando un pueblo llamado "Tin" (Тінь), que dependía de la vólost de "Horodyshche" (Городище), en el uyezd de Pyriatyn de la gobernación de Poltava.^[4]​^[5]​

Su desarrollo urbano comenzó en 1895, cuando se hizo pasar por la zona el ferrocarril de Kiev a Járkov. Junto al pueblo de Tin se construyó una estación, que dio lugar al poblado ferroviario de Petrivka (Петрівка). En 1901, Tin y Petrivka se unieron para dar lugar al pueblo de Hrebinka, que adoptó su topónimo en referencia al escritor Yevhen Hrebinka, nacido en un jútir cercano al nuevo pueblo. En las décadas siguientes creció como nudo ferroviario, al salir de la estación de Hrebinka líneas secundarias a Nizhyn y Cherkasy. Su dependencia del ferrocarril se consolidó en el Holodomor de 1932-1933, cuando una parte importante de los campesinos locales murieron de hambre, mientras los trabajadores ferroviarios podían seguir comiendo.^[6]​^[7]​^[8]​

En 1935 se abrió aquí un centro de reparación de vagones, y el pueblo pasó a ser la sede de su propio raión. En 1938 se abrió un depósito de locomotoras, y la localidad fue ascendida al estatus de asentamiento de tipo urbano. En 1958 se anexionó al casco urbano como barrio el hasta entonces pueblo de Horodyshche, la antigua capital de la vólost. En 1959 adoptó el estatus de ciudad de importancia distrital. Antes de la formación del actual municipio en 2017, Hrebinka formaba por sí sola un ayuntamiento urbano sin pedanías.^[9]​^[10]​