The two countries had formed an alliance with each other.

Literal

Both-countries [topic-は] mutually alliance [object-を] had-formed.

互いに (mutually) and 同盟を結ぶ (to form an alliance, literally 'to tie an alliance') are diplomatic vocabulary. 結んでいた uses ていた (past ongoing state) — the alliance existed in the past.