피치 공주에게 종이접기 페스티벌에 초대받은 팔랑팔랑한 마리오와 루이지는 들뜬 마음을 안고 피치 성에 찾아가지만, 키노피오 타운의 모습이 평소와 다른 걸 느끼고 급히 피치 성으로 향한다. 그것이 새로운 모험의 시작이란 걸 알지 못한 채...

피치 성에 입장하면 평소와는 모습이 달라 보이는 피치 공주와 대화 후 지하 감옥에 갇히게 된다. 이벤트 영상이 끝난 후 감옥 안에 있는 손바닥 모양의 마법진에 다가가 X 버튼을 누르면 종이손이 나온다. 그 후 컨트롤러를 조작해 벽지를 떼어내면 '올리비아'를 구출할 수 있다.

올리비아 구출 후 감옥 오른쪽 구석에서 해머를 습득한다. 해머는 B 버튼을 누르면 필드에서도 여러 장애물을 파괴하거나 적을 공격할 수 있다. 해머를 사용해 위쪽에 있는 상자를 부수고 오른쪽으로 이동하면 쿠파 또한 잡혀 왔음을 알 수 있다.

이벤트 영상이 끝난 후 방 안으로 들어가 쿠파를 구출하고 오른쪽에 있는 상자 더미들을 파괴하면 마법진이 스폰 된다. 마법진을 이용해 벽지를 떼어낸 후 길을 따라 이동하면 점프로 공격하면 지금까지 진행 상황을 저장할 수 있는 S블록이 있다.

계단을 쭉 따라 올라오면 이벤트 영상 후 종이인형 병사들과 강제로 전투하게 된다. 페이퍼 마리오의 전투는 링을 회전시키거나 당겨서 모든 적을 한 줄 혹은 2X2 상태로 정렬시키는 퍼즐 X 액션 방식의 전투다. 모든 적을 올바르게 정렬시키는 데 성공했다면 1.5배의 공격력으로 적을 공격할 수 있다.

개인의 사고력에 따라 여러 가지의 경우의 수로 적을 정렬시킬 수 있다. 다만, 링을 조작하거나 취할 수 있는 액션의 수는 전투마다 정해져 있다.

전투 후 최종 보스인 '올리 왕'이 모습을 드러내고 피치 성을 종이리본을 사용해 감싼 뒤 산 정상으로 옮긴다. 쿠파피에로에 탑승해 피치 성에서 탈출하던 마리오와 동료들은 갑자기 나타난 종이리본에 부딪혀 뿔뿔이 흩어지게 되는 것으로 프롤로그가 막을 내린다.