Rakstos pirmoreiz minēta 1371. gadā. Kopš 14. gadsimta - Polijas sastāvā. 1546. gadā pilsētā tika izveidots pirmais sāls ieguves uzņēmums. Pēc Polijas Pirmās dalīšanas 1772. gadā pilsēta iekļāvās Austrijas impērijā (Austroungārijā) un bija tur līdz Pirmā pasaules kara beigām. 19. gadsimta beigās 75% no pilsētas iedzīvotājiem bija ebreji.
Pēc Pirmā pasaules kara Bolehiva iekļāvās jaunizveidotajā Polijas valstī. 1939. gadā, pamatojoties uz Molotova-Ribentropa paktu, PSRS iebruka Polijā, un Bolehiva tika iekļauta Ukrainas PSR. No 1941. gada līdz 1944. gada 7. augustam atradās vācu okupācijā. Vācu okupācijas laikā pilsētas ebreji tika iznīcināti. Pēc kara pilsētas poļu iedzīvotāji tika pārcelti uz Poliju. No 1991. gada - neatkarīgās Ukrainas sastāvā.