Окончив первым учеником Николаевскую гимназию в Воронеже, он вскоре поступил в Санкт-Петербургский технологический институт. Однако революционные события 1905 года захватывают Федотова, примкнувшего поначалу к радикальным социалистам. Арест и высылка за границу способствуют продолжению образования – Федотов изучает историю в Берлинском и Йенском университетах. Тогда же в Германии он оказывается под влиянием христианской гуманистической философии и постепенно отходит от марксистского материализма.
Осенью 1908 года Федотов возвращается в Россию и поступает на историко-филологический факультет Петербургского университета, где попадает в кружок выдающегося педагога-просветителя, убежденного европеиста Ивана Михайловича Гревса, вырастившего целую плеяду крупных историков и культурологов, среди которых Лев Карсавин и Владимир Вейдле. Увлекшись благодаря Гревсу проблемами европейского Средневековья, Федотов окончательно отходит от политики. Тем не менее он продолжает оставаться под надзором полиции и, подвергшись несколько раз обыскам и опасаясь ареста, уезжает по подложному паспорту в Италию, где работает в библиотеках Рима и Флоренции, зарабатывая на жизнь частными уроками в семьях богатых русских. Впоследствии в работе «Лицо России» (1918) Федотов писал о той огромной роли, которую сыграла Италия в его становлении как историка русской культуры: «Именно более глубокое погружение в источники западной культуры открыло великолепную красоту русской культуры. Возвращаясь из Рима, мы впервые с дрожью восторга всматривались в колонны Казанского собора; средневековая Италия делала понятной Москву».
Вернувшись в Россию, Федотов был приговорен к годичной ссылке и выбрал Ригу, где занялся подготовкой диссертации. После возвращения в Петербург он успешно сдал магистерские экзамены и был оставлен при университете, где вскоре получил приват-доцентуру по кафедре Средних веков, работая одновременно хранителем отдела искусств Публичной библиотеки.
Первую мировую войну Федотов воспринял как совместную борьбу россиян за свободу в союзе с западными демократиями. Февральская революция 1917 года была встречена им без восторга: он понимал, что русская демократия слишком хрупка и бессильна перед натиском разрушительных бескультурных сил. После Октября он остается на службе в Публичной библиотеке, продолжает заниматься наукой, посещает религиозно-философские кружки, участники которых надеялись на мирную эволюцию большевизма.
Тяжело переболев сыпным тифом, Федотов берет отпуск и уезжает в родной Саратов, где становится профессором кафедры средневековой истории. Вскоре, однако, он вынужден был покинуть университет из-за своего демонстративного отказа соблюдать советскую обрядность – посещение собраний, хождение на демонстрации и тому подобное. Убежденный христианин, Федотов решает вскоре вообще уволиться с госслужбы и зарабатывать переводами в частных издательствах, расплодившихся в годы нэпа: это обеспечивало приличный заработок, хотя и лишало госпайка, а также существенно повышало плату за квартиру и обучение дочери.
В 1925 году Федотов получает французскую визу и выезжает сначала в Берлин, а затем в Париж; через некоторое время к нему переезжает из России и семья. Работать и публиковаться во Франции по узкой специальности – медиевистике – оказалось невозможным (хороших специалистов было в избытке), и Федотов в поисках заработка начинает писать историко-публицистические статьи для эмигрантских журналов. Конкуренция и здесь была велика, но уже первые статьи-эссе Федотова («Три столицы» и «Трагедия интеллигенции»), опубликованные в 1926 году в парижском журнале «Версты», получили широкую известность в литературно-политических кругах русской эмиграции. На молодого автора обратила внимание редакция крупнейшего эмигрантского журнала «Современные записки», в котором Федотов затем многократно печатался, снискав себе славу «
В Париже произошло знакомство Федотова с другим русским эмигрантом – крупнейшим философом Федором Степуном, дружба и сотрудничество с которым продлилась долгие годы. Степун позднее вспоминал о первой встрече с Федотовым: «Впечатление было несколько неожиданное… Очень сдержанная речь с паузами и умолчаниями, тихий, но богатый интонациями голос; во внешнем облике, несмотря на заношенный пиджачок, нечто очень изящное, хрупкое и даже декадентское, что не встречалось у писателей-бытовиков и партийцев-общественников. Во всем образе нечто аристократически-отъединенное…»