10 września 1941 został zestrzelony, jednak zdołał dolecieć płonącą maszyną do linii frontu i nad swoim terytorium wyskoczyć wraz z załogą na spadochronach. W 1941 został członkiem WKP(b).
W marcu 1942 jego pułk został włączony do Lotnictwa Dalekiego Zasięgu i przemianowany na 4 pułk Lotnictwa Dalekiego Zasięgu, w którym Jewdokimow był dowódcą klucza, a od 1943 dowódcą eskadry. Pilotując samolot Ił-4 walczył w bitwie pod Moskwą, bitwie pod Stalingradem (gdzie wykonał 36 lotów bojowych), w bitwie pod Kurskiem (wykonując 20 lotów bojowych), brał udział w operacji smoleńskiej, białoruskiej (lato 1944), nadbałtyckiej (jesień 1944), wschodniopruskiej (zima 1945), pomorskiej (marzec 1945) i berlińskiej (wiosna 1945). Wielokrotnie wykonywał naloty na głęboki tył wroga, bombardując obiekty w Gdańsku, Tilsicie, Warszawie, Królewcu, Budapeszcie i Berlinie. W styczniu 1944 brał udział w serii ataków na centra przemysłowe w Finlandii. W 1943 został zestrzelony przez niemieckie myśliwce za linią frontu, jednak wraz z załogą zdołał wyskoczyć na spadochronie i z pomocą mieszkańców w ciągu 7 dni przejść przez linię frontu. Wykonał 270 lotów bojowych, w tym 256 nocnych.