У V ст. західна частина Римської імперії впала під ударами внутрішніх повстань і натиску варварських племен. Східна частина Римської імперії (Візантія) з центром у Константинополі вціліла і протягом декількох століть залишилася одним з наймогутніших держав середньовіччя.
Саме Візантія, з її імператорами, пишним придворним штатом і кривавими палацовими переворотами, виявилася особливо придатною для подальшого вдосконалення мистецтва шпигунства.
У 516 р в багатому Константинополі натовп глядачів захоплено вітала яка виступала на сцені молоду красиву актрису. Важко сказати що-небудь про якість виконання нею візантійських танців. Наші джерела не дозволяють судити про це, - вони звертають увагу на інше: актриса порушила суворе постанову міської влади, що забороняли виступ без одягу. А тонка золотий ланцюг, що окреслює талію Феодори (так звали актрису), навряд чи могла пом'якшити обурення церковних моралістів. Втім, незабаром і моралісти вважали за краще прикусити язики. Актриса стала дружиною багатого візантійського вельможі, але незабаром була кинута чоловіком, який не бажав терпіти її невірність і покривати витрати по її нестримного марнотратства.
Деякий час Феодора вела злиденне життя в Олександрії. Одного разу вона побачила віщий сон, що передрікав їй стати дружиною могутнього монарха. Феодора повернулася в Константинополь і почала зображати раскаявшуюся грішницю. Уявна скромниця з ранку до ночі пряла в невеликому будиночку, де вона оселилася. Дослідної кокетці вдалося привернути увагу знатного патриція Юстиніана, племінника імператора. Зрозуміло, імператриця, тітка Юстиніана, заборонила йому і думати про одруження на колишній актрисі. Але незабаром тітка померла, Феодора стала дружиною Юстиніана, а в 527 р коли Юстиніан вступив на трон, Феодора була коронована імператрицею. Вона мала величезний вплив на чоловіка. З перших років правління Феодори проявився її розум, безмежна жорстокість і повна нерозбірливість у виборі засобів, необхідних для досягнення цілей.
Колишня танцівниця і її чоловік тиранически управляли величезною імперією, яка охоплювала половину відомого тоді світу. Для зміцнення своєї влади Феодора вдавалася до послуг великого числа шпигунів, які стежили за всіма її ворогами або просто людьми, вселяє їй підозра. Імператриця невтомно благочестиво повторювати, інструктуючи своїх агентів: «Клянуся Ісусом, що живуть вічно, якщо ви не виконаєте моїх наказів, з вас живих здеруть шкіру». Феодора померла в 548 р після 22 років правління.
Візантія розвивала систему розвідки і в наступні століття. Навпаки, в Європі середні століття були періодом занепаду розвідувальної служби. Хоча іноді траплялися виключення з правила.
Данці не приховували свого презирства до переможеного ворога, якому чутка приписувала велике військове мистецтво. У нього залишилося зовсім мало воїнів і ніколи вже не буде достатньо сил, щоб чинити опір звиклому до перемог хороброму датському війську - ось про що розмовляли датські дружинники, які зібралися біля намету Гутрума. Їх розмова перервали звуки музики. Грав музикант. Це був сакс, погано розумів по-датському, вже не перший тиждень перебував у стані Гутрума. До нього встигли настільки звикнути, що навіть дивувалися, якщо він протягом декількох днів не з'являвся в галері. Бідний музикант носив за плечима мішок, куди складав залишки їжі, які недбало кидали йому датські дружинники, які відібрали багато зерна і худоби у переможених саксів.
Арфіст був хорошим музикантом. Часом він закривав очі і, загадково посміхаючись, як би в забутті, витягував зі свого інструмента тихі звуки, які не заважали, а скоріше оживляли бесіди суворих воїнів. Так було і зараз, коли під акомпанемент арфи Гутрум і його наближені детально обговорили план остаточного розгрому дружини короля Уессекса. Данці були великими майстрами використання прийомів і хитрощів на поле бою, і зараз вони заздалегідь домовилися, як діяти під час майбутнього нового бою з саксами.
Незабаром почався похід. Данці рушили на ворога. Але їх чекало гірке розчарування: виявилося, король Уессекса Альфред мав у багато разів більше воїнів, ніж припускали данці. Їх загони були оточені саксами.
Не допомогли і військові хитрощі - сакси як ніби заздалегідь знали, що зроблять воїни Гутрума. Данці мали просити світу, обіцяючи підкоритися правителю Вессекса. Гутрум і його наближені прийшли в табір Альфреда для переговорів і там побачили розгадку своїх невдач. Король Альфред прийняв датських воїнів з добре знайомої їм посмішкою, тримаючи арфу в лівій руці.
Дуже характерно, що і пізніше в Європі не змогли оцінити значення знаменитого подорожі Марко Поло в багато країн Азії і його рясніли важливими відомостями розповіді про Сході. Те, що з великими труднощами дізнаватися купці, зазвичай становило їх «торгову таємницю». Навіть коли вони готові були поділитися нею, королі і князі не поспішали ознайомитися з привезеними здалеку новинами.
На Сході розвідка відігравала важливу роль в армії Чингіз-хана і його спадкоємців. Появі монгольської армії завжди передували дії розвідників, яких часто вербували з числа іноземних купців. Розвідники повідомляли дані про дороги, фортецях, чисельності гарнізонів, надавали відомості політичного характеру, що дозволяють полководцям Чингіз-хана орієнтуватися в завойовується країнами.
В період Пізнього Середньовіччя Європа вдається до свідомої посилці розвідників в східні країни для добування інформації. Так, в 1421 г. англійський король і герцог Бургундський спільно направили на Середній Схід досвідченого воїна і дипломата Джилберта де Ланнуа з сімома супутниками, щоб вони склали докладний звіт про становище в відвіданих ними державах. Приблизно через десять років з такою ж місією від Бургундського герцога був посланий лицар Бертрандон де ла Брокьер. Грецький гуманіст Костянтин Ласкаріс в кінці XV ст. їздив туди ж в якості секретного агента правителя Флоренції Лоренцо Медічі.