Естественно, опыт бывшего русского морского летчика оказался востребованным. Марченко служил в бомбардировочной авиации (первоначально в чине младшего лейтенанта; 10 марта 1936 г. он получил чин лейтенанта) и выполнял самые разнообразные и сложные задания. Например, он оказался одним из немногих летчиков, выполнявших ночные полеты. Марченко принимал участие в снабжении с воздуха монастыря Вирхен де ла Кабеса, расположенного на юге Испании в провинции Хаен. В монастыре и расположенном рядом дворце Эль Люгар Нуэва укрылись жандармы упомянутой провинции вместе со своими семьями. Осада монастыря продолжалась с 14 сентября 1936 г. по 1 мая 1937 г. Самолетами из Севильи осажденным регулярно два раза в сутки, в т. ч. и ночью, сбрасывались продукты питания, боеприпасы и почта. Выполнение этой задачи оказалось связано с немалыми трудностями, т. к. требовалось летать на предельно малой высоте, подвергаясь ежесекундно риску быть сбитым огнем зенитных орудий.
Марченко участвовал также в сражении у Брунете (наступательная операция республиканских войск, проведённая в июле 1937 г. с целью окружения и разгрома мадридского корпуса франкистов), бомбардировке важного торгового порта Альмерия (январь 1937 г.), в арагонской кампании 1937 г.
Поскольку в Испании еще не было достаточного количества летчиков, умевших летать ночью, вся тяжесть ночных полетов легла на известного испанского летчика капитана Карлоса де Айя Гонсалеса и самого Марченко. В марте 1937 г. капитан Айя организовал 1-ю ночную эскадрилью бомбардировщиков Ju-52, в составе которой и стал служить Марченко (с 5 марта). После того как монастырь монастыря Вирхен де ла Кабеса взяли республиканцы, Всеволода Михайловича Марченко перевели на сарагосский фронт. Рагозин вспоминал: «