В латинской хронике Вильгельма Тирского сообщается о столкновениях отрядов крестоносцев Боэмунда Тарентского с еретиками (1097 г.). Охридский архиепископ Феофилакт (1090–1108 гг.), неоднократно удалялся из Охрида в Битолу. Сохранились два его письма, адресованных не названному по имени Пелагонийскому епископу. В 1201 г. болгарский воевода Добромир Хрис в союзе с византийским вельможей Мануилом Камицей захватил Битолу и Прилеп. В период между взятием крестоносцами Константинополя и восстановлением Византийской империи (1204–1261 гг.) Битола неоднократно попадала под власть то болгарского царя, то эпирского деспота, то никейского императора. При короле Милутине (1282–1321 гг.) сербы отвоевали у Византии значительную часть Македонии, включая Скопье, в том числе ряд городов Прилепской области, относившихся к Битольской епархии. Причём эти земли Милутин подчинил власти сербского архиепископа. После победы сербского короля Стефана Дечанского в Вельбуждской битве (1330 г.) Битольская епархия утратила Велес. Сама Битола осталась во владениях Византии, а Битольская епархия продолжала существовать в рамках Охридской архиепископии, потеряв значительную часть своей территории. Завоевание Македонии было завершено сербским царём Стефаном Душаном (1331–1355 гг.). Своим хрисовулом он передавал монастырь Трескавец, до этого находившийся в ведении Битольского епископа, в прямое подчинение Охридскому архиепископу. В 1360 гг., в период раздробленности государства, Битола оказалась во владениях кралей Вукашина и Марко (с 1371 г.). В 1382 г. Битола оказала упорное сопротивление армии султана Мурада I. По словам турецкого хрониста Сеадеддина, город был взят «после жестокой битвы и кровавой осады». Битола была отдана в управление главному полководцу султана Евронесу-бегу, поскольку являлась важным военным центром из-за своего стратегического положения в регионе. В период османского владычества Битола являлась главным городом вилайета в Западной Македонии и называлась Толи-Монастир или Монастир. В 1580 гг. Битольская епархия была возведена в ранг митрополии и имела подведомственную Прилепскую епископию, в которую входил город Велес. Во второй половине XVI в. (до 1585 г.) Битольскую кафедру возглавлял епископ Григорий, известный книжник, который перевёл на церковнославянский язык сборник проповедей Дамаскина Студита, что послужило отправной точкой для создания традиции славянских дамаскинов. Битольский митрополит Иеремия три раза ездил в Россию (1586, 1604 и 1622 гг.) и получал от московского государя денежную помощь и дары. В XVII в. Прилепская епископия слилась с Битольской митрополией. После Австро-турецких войн 1683 и 1689 гг. Битола, как и другие македонские города, временно пришла в упадок, и число её жителей сократилось до 12 тыс. Во второй половине XVII в. из Битольской епархии была выделена самостоятельная Велесская епархия. В 1767 г. с упразднением Охридской архиепископии Битольская (Пелагонийская) митрополия перешла под юрисдикцию Константинопольского патриархата. С целью принизить значение Охрида Константинопольский патриарх пожаловал ряду македонских архиереев почётные титулы, причём Пелагонийский митрополит получил титул «экзарх Верхней Македонии».