The story is set in a world where humanity has lost control of the seas. The threat that has taken over the seas is the "deep sea fleet." The only ones who can counter this threat are Kan-musume (literally, warship girls), girls who possess the spirit of naval vessels from days gone by.

The base for the fleet arrayed against the "deep sea fleet" is Chinjufu. There, many various Kan-musume have gathered to live together and work hard everyday in training and other matters. One day, a Kan-musume arrives at Chinjufu, She is a special class of destroyer. Her name is Fubuki. "I am Fubuki! Nice to meet you!" Fubuki's story — as well as the Kan-musume's story — begins now.

[Source: official website via ANN]