22세기 말. 갑자기 화성방면에서 나타난 로봇부대 목성 도마뱀은 압도적인 전투력으로 화성을 제압하고 달의 뒷면까지 진출했다. 그들은 지구에 '튤립'이라 부르는 모함을 강하시켜 지구의 각 거점을 직접 공격하기 시작했다. 그런 전란 중, 민간기업 네르갈 중공은 목성 도마뱀의 공격 이후에 화성에 남겨진 사람들을 구하기 위해 '스캐팔레리 프로젝트'를 계획, 그 중심이 되는 실험전함 ND-001 나데시코를 제작한다. 나데시코에 탑승할 크루들은 '능력만 있다면 성격은 어찌되든 상관없다'는 방침으로 모아 어중이떠중이같은 인재들만 가득 모인다. 그리고 대망의 출항 당일, 화성 출신인 텐카와 아키토는 우연히 다시만난 소꿉친구 미스마루 유리카를 쫓아 출항직전의 나데시코에 오르게 된다. 아키토는 나데시코의 요리사로 채용되지만, 인형병기를 조종할 수 있는 IFS 처리를 받았다는 이유로 반강제로 인형기동병기 '에스테발리스'의 파일럿이 된다.
