В 1898 г. семья Евдокимова переехала из Семереченской области на жительство в г. Читу. С апреля 1905 г. сторож и списчик вагонов на станции Чита Забайкальской железной дороги, в январе 1906 г. как член рабочей боевой дружины самообороны участвовал в захвате вагонов с оружием и в вооруженных выступлениях железнодорожных рабочих в г. Чите. В январе 1906 г. в ходе боев с частями карательной экспедиции под командованием генерал-лейтенанта А. Н. Меллер-Закомельского был ранен осколками снаряда в обе ноги и лечился в госпитале. В июне 1906 – феврале 1908 гг. конторщик железнодорожной мастерской на станции Чита, конторщик товарной конторы железнодорожной станции Чита-1, затем арестован полицией и заключен в Читинскую тюрьму. В мае 1908 г. освобожден, с июня 1908 г. ученик наборщика в типографии «Азиатская Русь» (г. Чита). В феврале 1909 г. был арестован полицией за принадлежность к «Всероссийскому нелегальному союзу железнодорожников Читинского района» и осужден Иркутским военно-окружным судом к 4 годам каторжных работ[115], замененных, как несовершеннолетнему на 2 года и 3 месяца тюремного заключения. Срок наказания отбывал в Александровском централе в г. Верхнеудинске, затем в мае 1911 г. освобожден из заключения и определен на поселение под гласный надзор полиции в г. Верхнеудинске Иркутской губернии. В октябре 1911 г. «за агитацию против самодержавия и возбуждение военного гарнизона в Березовке» был выслан на поселение под гласный надзор полиции в г. Камышлов Пермской губернии. В марте 1912 г. бежал с места поселения и перешел на нелегальное положение, работал в подпольных организациях анархистов-коммунистов в г. г. Харбине, Владивостоке, Имане, Хабаровске и Благовещенске (по некоторым данным входил в состав Сибирского летучего боевого отряда эсеров).
В июне 1912 – феврале 1913 гг. рабочий сельскохозяйственной артели «Тайга» (Иркутская губерния), затем на случайных поденных заработках в г. г. Благовещенске, Чите и Камышлове, неоднократно арестовывался полицией и высылался за пределы Иркутской и Пермской губерний. С мая 1914 г. безработный в г. Омске, с июля 1914 г. наборщик в типографии «Печатное дело» в г. Челябинске. В мае 1915 – декабре 1916 гг. конторщик Центрального союза потребительских обществ (Центросоюза) в Москве, в дальнейшем в связи с призывом на военную службу перешел на нелегальное положение, и выехал в г. Баку. С января 1917 г. счетовод Бакинской городской управы, с апреля 1917 г. рядовой 12-го запасного Сибирского полка, затем председатель солдатского комитета 12-го запасного Сибирского полка (г. Чита). После демобилизации в сентябре 1917 – марте 1918 гг. конторщик и председатель ревкома Центросоюза (г. Москва), одновременно участвовал в формировании отрядов Красной Гвардии Благуше-Лефортовского района г. Москвы, затем заведующий распределительно-справочным отделом Управления делами ВЦИК РСФСР. С ноября 1918 г. слушатель ускоренных курсов при Академии Генштаба РККА, с мая 1919 г. информатор и регистратор Учетно-распределительного отдела ЦК РКП(б), одновременно в мае 1919 г. участвовал в формировании диверсионных отрядов для работы в колчаковском тылу.
С июня 1919 г. в органах госбезопасности[116]: начальник ОО Московской губернской ЧК, в декабре 1919 г. откомандирован на работу на Украину, с января 1920 г. помощник начальника ЦУПЧРЕЗКОМа (по особым отделам) и начальник СОЧ ОО Южного фронта, с января 1920 г. заместитель начальника ОО Юго-Западного фронта, одновременно с августа 1920 г. начальник ОО Юго-Западного фронта, начальник тыла Юго-Западного фронта и помощник начальника ЦУПЧРЕЗКОМа. В ноябре 1920 – январе 1921 гг. начальник ОО Юго-Западного и Южного фронтов, одновременно начальник Крымской ударной группы, затем начальник ОО ЦУПЧРЕЗКОМа. С мая 1921 г. начальник СОУ и начальник ОО Всеукраинской ЧК – ГПУ УССР, с июня 1922 г. полпред ГПУ УССР по Правобережной Украине[117] и (с ноября 1922 г.) командующий войсками ГПУ на Правобережной Украине, одновременно в ноябре 1922 – июне 1923 гг. врид. начальника и начальник Киевского губотдела ГПУ. С июня 1923 г. полпред ОГПУ по Юго-Востоку России, с октября 1924 г. полпред ОГПУ по Северо-Кавказскому краю, одновременно (по совместительству): в 1924 – 1926 гг. начальник Административного управления и милиции Северо-Кавказского крайисполкома и в июле 1923 – октябре 1927 гг. начальник ОО ОГПУ СКВО.
В январе – ноябре 1926 г. находился на учебе на курсах при Социалистической Академии (г. Москва), затем вновь полпред ОГПУ по Северо-Кавказскому краю[118]. С октября 1929 г. начальник СОУ ОГПУ СССР и член коллегии ОГПУ СССР, с июля 1931 г. полпред ОГПУ по Ленинградской области (приказ о назначении был отменен). В августе 1931 – ноябре 1932 гг. полпред ОГПУ по Средней Азии, затем полпред ОГПУ по Северо-Кавказскому краю. В январе 1934 г. освобожден от занимаемой должности и откомандирован в распоряжение ЦК ВКП(б).