어드밴스 워즈의 이야기는 "필드 트레이닝" 튜토리얼 모드에서 시작됩니다. 오렌지 스타 국가가 이웃 국가인 블루 문과 전쟁 중이며, 블루 문 군의 지휘관 올라프가 등장합니다. 올라프는 갑자기 오렌지 스타 국가에 대한 침공을 명령하고 오렌지 스타 군과 전투를 벌입니다. 캠페인은 튜토리얼에서 시작된 이야기를 이어갑니다. 오렌지 스타 CO들의 사실상의 리더인 넬은 플레이어에게 오렌지 스타 군의 전술 고문 역할을 부여합니다.
플레이어는 게임 진행 중 네 개의 국가와 그 각각의 CO들을 통해 전쟁 노력을 따라갑니다. 처음에는 조언할 CO로 앤디 한 명만 선택할 수 있지만, 이야기가 진행됨에 따라 두 명의 오렌지 스타 CO인 맥스와 사미를 추가로 조언할 수 있는 선택지가 생깁니다. 각 CO는 고유한 장점과 단점을 가지고 있습니다. 플레이어가 조언할 CO에 따라 미션이 두 개 또는 세 개로 나뉘는 경우가 있으며, 이때 맵과 대화가 달라질 수 있습니다. 해당 미션을 완료한 후에는 이전 미션에서 선택한 CO에 따라 이야기 경로가 나뉘며, 다른 경로와는 다른 이야기가 전개되지만 결국 다시 주요 경로로 이어집니다.
그린 어스와의 전투에서 승리한 후, 앤디는 그린 어스의 CO인 이글에게 배신적인 공격 행위로 의심받게 됩니다. 오렌지 스타 국가를 침공한 블루 문 군대를 물리친 후, 오렌지 스타 군은 블루 문 국가를 침공하여 그들의 군대를 무찌릅니다. 블루 문 CO인 올라프와 그릿은 둘 다 이전에 오렌지 스타 군에서 일했던 CO였으나 블루 문으로 전향한 인물들로 밝혀집니다. 오렌지 스타 군의 의도가 단순히 다른 두 국가인 그린 어스와 옐로우 코멧을 통과하는 것이었지만, 이들 국가의 CO인 칸베이와 같은 인물들은 침공의 위협을 가정하고 오렌지 스타 군에 대한 전투를 선언합니다.
이후 그린 어스 CO 드레이크는 이글에게 오렌지 스타 군이 그린 어스를 공격하지 않았다고 말하며 "이 모든 갈등은 처음부터 조작된 것"이라고 전합니다. 한편, 옐로우 코멧 CO인 손자와 그릿은 실제 공격의 배후에 있는 인물을 찾으려 합니다. 이글이 앤디를 다시 만났을 때, 이글은 다시 앤디가 그린 어스를 공격했다고 비난하지만, 오렌지 스타 CO들은 결국 이글을 설득하여 앤디가 그린 어스를 공격하지 않았음을 알립니다. 이는 세 나라가 오렌지 스타에 대해 전투를 선언한 이유를 설명합니다. 그들은 앤디가 먼저 공격했다고 생각했기 때문입니다.
이글이 손자를 만났을 때, 손자도 이글에게 앤디가 공격의 배후가 아니라고 말하며 다른 누군가가 있다고 전하고, 그녀가 발견한 것을 보러 함께 갑니다. 신비로운 블랙 홀 군대가 스텀의 지휘 아래 진정한 적임이 드러납니다. 스텀은 앤디의 CO 더블갱어 클론을 사용하여 네 개의 국가 간에 전쟁을 일으켜 혼란을 초래하고 약화시킨 후 결국 정복하려 했습니다. 이 사실이 밝혀지자, 네 개의 국가는 블랙 홀을 그들의 땅인 코스모 랜드에서 몰아내기 위해 단결하며, 플레이어가 게임 중 선택한 경로에 따라 자동으로 CO가 선택됩니다.
The story of the Advance Wars begins in the "Field Training" tutorial mode, with the nation of Orange Star in a war against the neighboring nation of Blue Moon, with Olaf as the Blue Moon Army commanding officer (CO). Olaf suddenly ordered an invasion of the Orange Star nation and is in battle with the Orange Star Army. The campaign continues the story that started in the tutorial. Nell, the de facto leader of the Orange Star COs, gives the player the duty of a tactical advisor for the Orange Star Army.
The player follows the war effort through all four countries, with its own COs, over the course of the game. Starting with having only one choice of a CO to advise, Andy, the player will have a choice of two more Orange Star COs, Max and Sami, to advise as the story progresses, each with their own advantages and disadvantages. Depending on which CO is chosen by the player to advise, there are times when a mission is split into a choice of two or three, where the maps and dialog could be different. After completing that mission, the story paths could split up, depending on which CO was chosen in that previous mission, with the story differing from the other path, eventually leading back to the main path.
After winning a battle against Green Earth, Andy gets mysteriously accused by Green Earth's CO, Eagle, of committing a treacherous act of aggression against Green Earth. After defeating the Blue Moon troops that invaded the Orange Star country, the Orange Star Army then invade the Blue Moon country, defeating their troops. The Blue Moon COs, Olaf and Grit, are revealed to be COs whom both used to work for the Orange Star Army, but switched to Blue Moon. When the Orange Star Army's intention was to just pass through the other two countries, Green Earth and Yellow Comet, the countries' COs like Kanbei of Yellow Comet assume a threat of an invasion and declare battles against the Orange Star Army in their land.
Later on, Green Earth CO Drake tells Eagle that the Orange Star Army didn't attack Green Earth, saying that "This entire conflict has been orchestrated from the beginning." Meanwhile, Yellow Comet CO Sonja and Grit try to discover the person who is really behind the attacks. When Eagle meets Andy again, Eagle again accuses Andy of attacking Green Earth, to which the Orange Star COs eventually convince Eagle that it wasn't Andy who attacked Green Earth. This explains why the three nations have been declaring battles against Orange Star, as they thought Andy attacked them first.
When Eagle meets Sonja, Sonja also tells Eagle that Andy wasn't behind the attacks, saying it was someone else, and goes with her to see what she discovered. It is revealed that the enigmatic Black Hole Army, under the command of Sturm, is the true enemy. Using a CO doppelganger clone of Andy, Sturm stirred up war among the four countries in order to confuse, weaken, and eventually conquer them. Once this is revealed, the four countries unite to drive Black Hole out of their land, the Cosmo Land, with COs automatically chosen depending on the paths the player took during the game.