Назву села виводять від часів монголо-татарської навали в ХІІІ ст., коли жителі тікали в гірські ліси, де в долині річки начебто вирубали дерева і заснували поселення. Так появився верхній та ніжній “стин”, від якого згодом й утворилися назви двох сіл — Верхньої Стинави і Нижньої Стинави.
Віломий учений К. Тищенко пояснює походження основи назви Стин- від готського Sten — камінь, а другу частину назви -ава — від ahwa (ава) — вода. Тоді назва Стинава буквально означає “Кам’яна вода”, “Вода, що випливає з-під каміння”. За переказами, село засноване в ХІІІ ст.
У Верхній Стинаві є дерев’яний храм св. Миколи 1904 року — одна з типових церков початку XX ст., споруджена за проектом львівського архітектора Василя Нагірного.