В XI веке в Византийской истории начался новый подъём. Потеснённая в прошлые столетия в IX – X веках с запада и востока Византия, потеряв многие свои владения, словно получает второе дыхание. Наряду с военными успехами происходит рост экономической и культурной мощи государства.

Однако новый рассвет был не долгим. И прежде всего это было связано с падением императорской династии. Македонская династия, правившая в Византии в 867 – 1056 годах сходит с политической сцены. Центральная власть ослабевает, и большое значение получают знатные фамилии. На протяжении X – XI столетий в Византии происходит формирование аристократических семей, связанных общностью фамильных имён, историю которых возможно проследить по поколениям их представителей. При этом из числа общей массы византийской аристократии наиболее выделяется элита, узкая группа влиятельных семей, политическое и экономическое могущество которых основано на родстве с императорской династией.

Именно в это время, наряду с другими влиятельными аристократическими фамилиями, в исторических хрониках упоминается имя Никифороса Палеолога. Он был видным византийским военачальником при императорах Романе IV Диогене (1067 – 1071), Михаиле VII Дуки (1071 – 1078), Никифоре III Вотатиане (1078 – 1081), а также Алексее I Комнине (1081— 1118). Он был последним византийским наместником Месопотамии, уступленной туркам-сельджукам. Известно, что Никифорос погиб в сражении с апулийскими норманнами при Дураццо (Дуррес/Диррахий/Драч) в Албании 18 октября 1081 года. Когда утвердившийся на юге Италии, в Апулии и Сицилии, лидер норманнов Роберт Гвискар (1016 – 1085), воспользовавшись династическим кризисом в Константинополе, решил расширить свои владения в Македонии и Фессалии. Итальянские норманны разгромили византийцев при Дураццо. В битве участвовал и сын Никифороса Палеолога – Георгиос, руководивший византийским гарнизоном Дураццо, во время осады города норманнами. Он был приближённым императора Алексея I Комнина (1081 – 1118). О Георгиосе Палеологе упоминает в своих воспоминаниях принцесса Анна Комнина (1083 —1153), дочь императора Алексея I и Ирины Дукини.

Уже в то время семья Палеологов занимала видное место среди византийской аристократии, упрочив своё положение удачными браками. Никифорос Палеолог был женат на представительнице знатного армяно-византийского рода Куртикиев. А его сын Георгиос женился на Анне Дукини, сестре императрицы Ирины Дукины, супруги императора Алексея I Комнина, приходившейся внучкой царю Болгарии Ивану Владиславу (погиб 1018).

Его потомок Алексиос Палеолог (умер 1201/04), имел высший придворный титул деспота и женился на дочери императора Алексея III Ангела, правившего в 1195 – 1203 годах, принцессе Ирине. Их дочь Феодора Палеологиня вышла замуж за представителя другой семьи Палеологов, возможно, своего дальнего родственника великого доместника Фессалии, губернатора области на Балканах, Андроникоса Палеолога (1190 – 1248/52, Салоники).

В XI – XIII веках известно ещё несколько различных аристократических семей, представители которых занимали важные посты в императорской администрации и армии использовавших фамильное прозвище Палеологов. И хотя точные связи между этими семьями не установлены, но вполне очевидно, что они происходили из одного рода, связанного родственными узами с другими аристократическими фамилиями, в различное время правившими в империи, Дуками, Ангелами и Комниными, что позволило им присоединить к своему имени фамильное прозвище более знатных родственников.