Назва села походить від річки Колочавки. Заснували поселення у першій половині XV століття втікачі від кріпацького гніту.
Про мешканців Колочави чеський письменник Іван Ольбрахт писав у романі «Микола Шугай — розбійник»: «Це правнуки бунтівних невільників, які втекли від канчука і шибениць, підстаростів і отаманів пана Йосифа Потоцького, правнуки повстанців проти здирства румунських бояр, турецьких панів і мадярських магнатів».[1]
У глибоких улоговинах між горами втікачі на деякий час знаходили притулок і звільнення від кріпацького ярма. Кожен поселенець будував собі хатину з маленькими вікнами, глиняною долівкою, солом’яною або дерев’яною покрівлею, без комина, з вогнищем посередині. Навколо неї пізніше будували житла сини й родичі; хутори розросталися й перетворювалися на присілки. При цьому вони зберігали свої історичні назви (від річки, від прізвища першого поселенця тощо). Центром Колочави став хутір Лаз.
Територія вздовж Тереблі в епоху середньовіччя часто переходила від одного феодала до іншого. Вже з 1365 року в долині Тереблі 6 осад належали феодалам румунського походження Балку і Драгу та нащадкам останнього — Драгфійовцям. У першій половині XV століття ці землі дісталися феодалам Білкеям, які в 1463 році передали їх своїм родичам — Урмезеям. Це і є перша письмова згадка про Колочаву.
Після 1526 року долина Тереблі потрапила до складу Семиградського князівства. Всі ліси ввійшли до складу Хустської домінії, а населення було підпорядковане Хустському замку.
Важливою пам’яткою давньої української літератури початку XVIII століття є «Збірник Петра Колочавського», у якому поміщено низку апокрифічних оповідань про антихриста і ходіння Богородиці по муках. У збірнику згадані «Володимер, монарха руский» та «Антиля, крол венгерский». Опис та аналіз «Збірника Петра Колочавського», мова якого «була далеко чистіша, як деяких закарпатських писателів із кінця ХІХ ст.», тобто москвофілів, опублікував у 1922 р. відомий український дослідник Володимир Гнатюк.[2]
З 1842 року селище мало власну символіку: печатку з типовим для старого Закарпаття геральдичним сюжетом — зображенням лісоруба з сокирою, перед яким стоять два дерева, а вгорі, себто на небі, — сонце й півмісяць (алегоричний символ християнського віровчення — відповідно Нового й Старого Заповіту Біблії).
