Уперше містечко згадується у 1419 році як село і центр невеликих володінь на перехресті трактів із Замостя на Волинь і Литву, а також з Любліна до Белза. Вже у 1538 році місто отримує магдебурзьке право. 

До 1951 р. Варяж належав до Польщі, а 15 лютого 1951 р. був переданий до складу УРСР. Місто втратило свій міський статус та навіть назву. 1991 року історична назва “Варяж” повернута, але давнє місто дотепер залишається селом.

У середмісті розташована церква Успіння Пресвятої Богородиці, яка була зведена у 1784 році як костел, а 1818-го перебудована в церкву. Зараз відреставрований храм діє.

Та найвеличнішою спорудою цього давнього містечка є маловідомий костел доби ранішнього бароко, пам'ятка архітектури України, яка носить ім’я св. Марка. 

Побудований храм був у 1688 – 1693 рр. за проектом 

В. Ленартовича у стилі бароко, названий на честь покровителя містечка св. Марка, який зображений на старому гербі Варяжа. Донині тут збереглися фрески, виконані ще у 1810 р. С. Строїнським. Фундатором комплексу монастиря отців-піарів вважається місцевий магнат Матчинський, його портрет зберігся у храмі. Розміри костелу справді вражають, а ще більше – інтер’єрні розписи, які невідомо завдяки якому чуду ще можна побачити, проте кожен наступний день може стати для них останнім, адже без даху їм зовсім недовго залишилось жити. Та храм вартий того, щоб його побачити.