All the soldiers were standing in a line.

Literal

Soldiers [subject-が] all lined-up were-standing.

並んで立っていた stacks two verbs: 並ぶ (to line up) in て-form provides the manner, and 立つ in ~ていた form describes the ongoing state. This 'て-form + another verb' pattern chains actions or adds manner to the main verb.