Konpeki No Kantai is based on the anime series Deep Blue Fleet, which, in its turn, is based on the novel of the same name by Yoshio Aramaki. The game follows the story of the anime since the first episode. It is set in an alternate universe, following a fictional story of a real historical character, admiral Isoroku Yamamoto (1884 -1943), the commander of the Japanese fleet during World War II. In reality, he was killed during a plane attack by American forces. However, in the anime (and the game) he is miraculously transported on board of the ship Nisshin, shortly after the battle of Tsushima, in 1905. Afterwards, he uses his knowledge from the future to make sure that Japan will be the most powerful country in the world.

The game re-creates the pseudo-historical battles against USA during the alternate World War II, such as depicted in the anime. It is a turn-based strategy game with heavy emphasis on naval combat. Controlling the Japanese Deep Blue Fleet, the player has the ability to micro-manage every aspect of it, including customizing waships, assigning soldiers, and even creating new weapons to be deployed in battles.