Soldiers are first seen in the cutscene after leaving Abadis Forest, speaking with General Gaius about Dust. The first encounter with them is in a scene at the end of Blackmoor Mountains, at Zeplich Village, but most of them are fought in the assault in Everdawn Basin.
Soldiers have a different fighting style than the other enemies in the game, by having a tendency to wait for Dust or the moonblood warriors to strike first, parry the attack, and then dash to attack from behind or forward, making them hard to fight. The best way to dispose of these enemies is with the Aerial Dust Storm when they are jumping, as they can't parry this move (soldiers staying on the ground still can parry it). Jumping towards a soldier forces them to jump too, leaving them open for attack, so they are easy prey to the Aerial Dust Storm. Combine this move with Fidget's fireball projectiles (and thus activating her special "fire pillars" attack) for a deadly combo.