Trebinje is a town in the Herzegovina region.
Dubrovnik airport (IATA: DBV) is just across the Croatian border and has direct flights from many cities in (mainly Western) Europe. Don't expect any direct transfers though; you would first have to travel into Dubrovnik and catch a regular bus to Trebinje there.
Trebinje has a bus station, which even though having been finished for quite some time, is still closed as of June 2015. The platforms however are in use and there are multiple daily departures to Dubrovnik, Mostar, and Podgorica. Ask your hostel/hotel for the correct departure times, do not trust online schedules or the schedule posted at the bus station!
The town centre is best (and only) explored on foot.
- Arslanagića most (Perovića most) (From the old town cross the main bridge, then turn left and walk the path along the river). Built in the 16th century, this Ottoman bridge used to connect the road between Dubrovnik and Istanbul. In the sixties it was moved 5km brick-by-brick to Trebinje to prevent being demolished for the building of a dam. Bring some beers from the shop and enjoy the sun setting over the hills. Free.
- Stari grad (walk through one of the two old city gates). Whereas in many other nearby cities the old town has become a tourist trap (I'm looking at you Dubrovnik), between these old city walls people still go about their daily lives as normal. It is home to two beautiful old mosques, small alleyways, a museum and a couple restaurants as well. Small, but very charming indeed.
- Saturday market (central square just outside the old town, follow your nose). Every saturday women from the surrounding villages come to Trebinje to sell fruit & vegetables from their own garden at the market. Always fresh, cheap and by definition organic. Other items you can buy include homemade rakija, cheese and clothing. Be there early!
- Hostel Polako, Svetozara Corovica 8 (walk into town, ask for Havana Club, it's right next door), ☎ +387 66 380 722, e-mail: firstname.lastname@example.org. Small indie hostel run by an American girl and Polish guy. Including giant tasty breakfast and friendly, relaxed atmosphere. Literally next to the old town walls. Dorm bed 24 BMK, Double room 60 BMK.
- Red Door Hostel, Niksicki put 17, ☎ +387 59 280 114, e-mail: email@example.com. Check-in: 14:00 - 22:00, check-out: 11:00. Choice of many dorms and an apartment too. 1.5 km from the old town. 6-bed dorm 20 BMK.
- Hotel Platani, ☎ +387 (59) 274 050, e-mail: firstname.lastname@example.org. Four-star hotel in the most beautiful part of town. Double room 85 BMK.
Mostar is a logical choice, or head to the coast to Dubrovnik.