В V в. западная часть Римской империи пала под ударами внутренних восстании и натиска варварских племен. Восточная часть Римской империи (Византия) с центром в Константинополе уцелела и на многие столетия осталась одним из самых мощных культурных государств средневековья.
Именно Византия с ее императорами, пышным придворным штатом и кровавыми дворцовыми переворотами оказалась особенно подходящей страной для дальнейшего совершенствования разведывательной службы.
При императоре Юстиниане (VI в.) была налажена слежка за всеми врагами императора Его жена властная Феодора, бывшая танцовщица, не уставала повторять своим шпионам: «Клянусь Иисусом, живущим вечно, если вы не исполните моих приказаний, с вас живых сдерут кожу».
Внешняя разведка при Юстиниане была значительно менее эффективной, она работала хуже чем при его предшественниках. Прокопий, византийский историк-современник Феодоры, писал: «Шпионы были организованы следующим образом. Некоторое количество людей было взято на содержание государства, с тем чтобы они посещали враждебные страны, особенно персидский двор, якобы по торговым делам и внимательно наблюдали, что там происходит» Таким образом после своего возвращения они имели возможность сообщать планы враждебных государств. Императоры, получив заранее тайные предостережение принимали предосторожности и никогда не бывали захвачены врасплох. Прокопий сообщает, что такая система существовала еще у мидийцев, потом у персов и римлян. Юстиниан, не следовавший в этом отношении примеру других римских императоров поплатился потерей важных владений.
На Западе оригинальную форму разведки изобрел вождь реи франков Хлодвиг, истребивший своих родственников, чтобы не было претендентов на его престол. «Много и других королей убил Хлодвиг, — повествует в своей хронике Григории Турский, — даже ближайших своих родных, опасаясь, чтобы они не отняли у него королевства, и таким образом распространил свое владычество на всю Галлию. Но однажды, когда его люди собрались к нему, он, как рассказывают, стал говорить им: «Горе мне, я теперь как странник между чужими, и нет у меня родственника, который помог бы мне, случись со мной беда». Однако, добавляет летописец, Хлодвиг говорил так вовсе не потому, что жалел погибших. Просто он хотел узнать, не уцелел ли случайно кто-либо из родни, чтобы тут же его прикончить...
В общем средние века были временем упадка разведывательной службы. Бывали, правда, исключения из правила. Король англосаксонского Уэссекса Альфред (IX в.), переодетый арфистом, проник в лагерь датчан, захвативших б6льшую часть Британии, выведал их планы и нанес им поражение в бою. Это был, кажется, единственный случай, когда монарх лично исполнял роль разведчика.
Знаменитый английский король Ричард Львиное Сердце, возвращаясь из второго крестового похода, бесследно исчез где-то в пути (он был арестован и содержался в крепости герцогом Австрийским). Отыскать Ричарда взялся трубадур Блондель Нельский. Он проехал по дорогам всей Германии, распевая песни, сочиненные Ричардом. Король услышал начало одной песни и из окна темницы пропел в ответ следующий куплет. Однако в целом организация разведки оказалась не под силу феодальным княжествам, из которых состояла Европа. Во тьме средневековой ночи мало что знали даже не об очень дальних странах.
Среди разведчиков этого периода заслуживает упоминания английский рыцарь сэр Томас Тэрбервилл. Во время англо-французской войны он был захвачен в плен, после чего поступил на службу к французскому королю Филиппу IV Красивому. За это Тэрбервиллу было пожаловано королем значительное земельное владение. В 1295 г. сэр Томас отправился на родину, оставив во Франции в качестве гарантии своей верности королю Филиппу заложниками двух своих сыновей. Ему было поручено поднять восстание в Шотландии и Уэлсе. В Англии Тэрбервилл был с почетом принят Эдуардом I, который назначил опытного воина, вырвавшегося из вражеского плена, членом королевского Совета. Тэрбервилл был разоблачен, когда было перехвачено его разведывательное донесение в Париж.
В средние века не было полностью утрачено древнее искусство шифрования корреспонденции. Например, император Лотарь (840-855 гг.) однажды послал различные сообщения своим сторонникам, замаскированные под цитаты из Священного писания. Впрочем, даже нехитрые коды оказывались обычно слишком сложной вещью. В эпоху, когда мало кто мог прочесть и простое письмо, редко было нужно прибегать к их шифровке. Только в конце средневековья тайнопись широко вошла в практику дипломатов различных итальянских государств, особенно Венеции. Новые замысловатые шифры не сразу были освоены в других странах. В испанских архивах сохранились шифрованные донесения послов, на полях которых рукой озадаченных канцеляристов выведено: «нельзя ничего понять», «бессмыслица», «потребовать, чтобы прислали другую депешу»...
В Азии разведка играла немалую роль во время завоевательных походов Чингиз-хана и его преемников. Правилами монгольской армии предусматривалась проверка донесений шпионов с помощью допроса пленных. Чингиз-хан предписывал также вылавливать и жестоко расправляться с вражескими разведчиками, которых обнаруживали в монгольском стане.
В средневековье начала практиковаться засылка из Европы разведчиков в восточные страны для добывания информации. Так, в 1421 г. английский король и герцог Бургундский совместно направили на Средний Восток опытного воина и дипломата Ажилберта де Ланнуа с семью спутниками, чтобы они составили подробный отчет о положении в посещенных ими государствах. Примерно через десять лет с такой же миссией был послан от Бургундского герцога рыцарь Бердрандон де ла Брокьер. Одетый в восточный костюм, он сумел побывать во многих ближневосточных странах, изучал языки, на которых говорили местные жители. Греческий гуманист Ласкарис в конце XV в. ездил туда же в качестве секретного агента правителя Флоренции Лоренцо Медичи. Число тайных лазутчиков, которые засылались преимущественно из Италии на Восток, все время увеличивалось.