El topónimo Trebinje proviene de la ciudad medieval de Travunia, perteneciente al estado de Raška. Fue probablemente construida por los eslavos en un antiguo asentamiento romano abandonado por los sarracenos en 840. A mediados del siglo X, Constantino Porphyrogenito lo menciona bajo el nombre de Terbunia. Se encontraba en el camino de Ragusa a Constantinopla, atravesado, en 1096, por Raimundo IV de Tolosa y su Primera Cruzada. Bajo el nombre de Tribunia o Travunja (la Trebigne de los Ragusos), perteneció a la Serbia Imperial hasta 1355. Trebinje se convirtió en una parte de la ampliación del estado bosnio medieval, bajo Tvrtko I de Bosnia en 1373. Hay una torre medieval en Gornye Politse cuya construcción se atribuye a menudo a Vuk Branković. El viejo monasterio de Tvrdoš se remonta al siglo XV.

En 1482, junto con el resto de Herzegovina, fue conquistada por el Imperio otomano. El castillo de la ciudad antigua fue construido por los turcos en el lugar de la fortaleza medieval de Ban Vir, en la ribera occidental del río Trebišnjica. Las murallas de la ciudad, la Plaza de la Ciudad Vieja, y dos mezquitas, fueron construidas a comienzos del siglo XVIII por la familia Resulbegovic. El puente Arslanagić fue construido originalmente en el siglo XVI en la aldea de Arslanagic, 5 km al norte de la ciudad, por Sokollu Mehmet Bajá, y era administrado por la familia Arslanagic. Se trasladó más cerca de Trebinje (1 km) a finales de los años 1960. El puente Arslanagic es una de los puentes turcos más atractivos de Bosnia y Herzegovina. Cuenta con dos arcos grandes y dos pequeños de medio punto.

Durante el período de administración del Imperio austrohúngaro (1878-1918) fueron construidas varias fortificaciones en las colinas circundantes, y había una guarnición con sede en la ciudad. También se modernizó la ciudad en expansión hacia el oeste, construyendo la actual calle principal, así como varias plazas, parques, nuevas escuelas, plantaciones de tabaco, etc.

Trebinje creció fuertemente en la era de Tito, en la República Socialista Federal de Yugoslavia entre 1945 y 1990. Es especialmente desarrollado su potencial hidroeléctrico (energía hidroeléctrica) con sus embalses, lagos artificiales, túneles, y varias plantas hidroeléctricas. Este desarrollo industrial trajo gran aumento de la población urbana.

Debido a su gran mayoría de población de etnia serbia, y a su gran proximidad con Croacia, durante la guerra de Bosnia fue escenario de combates entre el Ejército de la República Srpska y los de la coalición bosnio-croata,[1]​ y muchos de sus monumentos y restos de cultura musulmana fueron destruidos por los serbios. Después de los Acuerdos de Dayton, permanecieron en la ciudad sucesivos batallones españoles de IFOR, y luego de EUFOR como misiones internacionales de paz, hasta su salida definitiva en 2002.[2]​