충무김밥은 대체로 광복 이후 만들어진 음식으로 보고 있다. 이것의 유래에 대해서는 두 가지 구전이 전해진다.
경상남도 통영의 옛 지명은 충무인데, 이곳 사람들은 어업을 주된 생업으로 삼아 왔다. 어로 작업 특성상 선원들은 정해진 시간에 끼니를 해결하기 쉽지 않을 뿐만 아니라 격식을 갖추어 식사하기도 어려웠다. 그래서 간단히 끼니를 해결할 수 있는 음식을 준비하여 바다로 나갔는데 그중 하나가 김밥이었다. 그러나 여름철에는 밥과 반찬을 동시에 넣어 만드는 기존의 김밥은 상하여 먹지 못하는 일이 빈번하였다. 이를 해결하기 위해 김에 밥만 싸서 마련하고 무김치 등 반찬을 따로 준비하게 된 것이 현재 충무김밥의 유래가 되었다는 것이다.
다른 하나는 통영의 지리적 특성과 관련된다. 통영은 인근 도서 지역과 부산을 왕래하는 뱃길의 중심지였다. 그래서 옛 통영 여객선 터미널에는 사람들의 왕래가 끊이지 않았는데, 이들 승객들에게 주전부리 혹은 끼니용으로 팔던 것이 충무김밥이라는 것이다. 냉장 시설이 없는 배에서도 먹을 수 있도록 고안된 음식이어서 ‘뱃머리김밥’이라고도 불렸다.
이러한 두 가지 유래 설의 공통점은 여름철에 김밥이 변질하는 것을 방지하기 위하여 김밥과 반찬을 분리해서 만들었다는 것이다. 또한 충무김밥은 할매김밥, 꼬치김밥이라고도 한다.
충무김밥은 손가락 정도 굵기의 속이 없는 김밥과 깍두기, 오징어무침이라는 간단한 구성으로 되어 있다. 김은 6등분하여 고슬하게 지은 밥을 올려 말고, 데친 오징어는 양념(고춧가루, 간장, 다진 마늘, 파, 깨소금, 소금, 설탕, 참기름, 후춧가루)으로 무치고, 무를 어슷하게 썰어 소금에 절인 후 젓갈, 고춧가루, 다진 마늘, 다진 파로 양념한 것에 버무려 같이 곁들인다. 이외에 국물로 시래깃국도 같이 내놓는다. 깍두기 외에 섞박지라고 부르는 크게 썬 무김치를 곁들이기도 한다. 오징어 대신 낙지, 꼴뚜기, 어묵 등으로 대체하기도 한다.
어로 작업은 체력 소모가 상당한 중노동이고, 힘을 많이 써야 하는 일이어서 이들의 음식은 양이 많아야 했다. 따라서 과거의 충무김밥은 김밥보다 반찬의 양이 더 많아, ‘많고, 싸고, 투박한’ 느낌의 음식이었다. 충무김밥이 전국구 음식으로 명성을 떨치게 된 것은 1981년 ‘국풍81’에서 충무김밥을 선보인 이후이다. 이제는 전국 어디에서나 충무김밥을 먹을 수 있고 누구나 먹는 음식이 되어, 충무김밥은 양은 적어지고 가격은 비싸며 고급화되는 분위기로 바뀌고 있다.