No ano de 2096, os Wanzer (mecha "Walking Tanks") formam a espinha dorsal de muitas forças militares. A Comunidade Europeia está a desfrutar de um período de relativa paz quando é surpreendida por ataques repentinos a bases alemãs por parte de uma força misteriosa. Para investigar, decide-se enviar o EC Armor Tactics Research Corps, também conhecido como "Durandal". Dentro da Durandal, uma jovem recruta, Elsa logo se vê envolvida em uma conspiração internacional. Enquanto isso, a nação da Venezuela está tentando se separar dos Estados Continentais Unificados (U.C.S.). As Forças UCS são enviadas para restaurar a ordem e eliminar o Governador Diaz. Durante uma patrulha de rotina, o sargento. Darril e sua patrulha testemunham um avião de carga sendo abatido. Indo investigar, eles logo descobrem que se tratava de um avião que transportava parte do ouro de Diaz. Para soldados desmoralizados da UCS como Darril, isso cheira a oportunidade...
Front Mission 4 é um jogo de estratégia baseado em turnos onde o enredo alterna entre dois teatros de operação diferentes: Elsa e Darril. Controlando as forças wanzer de qualquer personagem, a história avança simultaneamente. A maioria das batalhas acontece em um mapa suspenso dividido em uma fase de Jogador e uma fase de Inimigo. Normalmente, um wanzer pode se mover uma vez e usar seus Pontos de Ação (PA) restantes para atirar no inimigo ou usar uma habilidade. O sucesso na batalha rende Pontos de Experiência, que são trocados por novas habilidades, como bônus de Fogo Rápido ou Evasão. Cada personagem tem um limite definido de slots de habilidade, que são preenchidos de forma diferente por habilidades. Embora cada personagem comece com uma preferência em habilidades, não há limitação sobre o que qualquer piloto pode aprender. O dinheiro encontrado no mapa (junto com os itens) ou ganho após uma batalha bem-sucedida pode ser usado para atualizar wanzers e comprar novas armas.
