Lịch sử của sushi ở Nhật Bản bắt đầu vào khoảng thế kỷ thứ 8. Các phiên bản gốc của sushi xuất hiện đầu tiên ở Đông Nam Á, đó là một cách bảo quản cá trong gạo lên men. Trong thời kỳ Muromachi (năm 1337 đến 1573), người ta bắt đầu ăn cơm và cá. Dưới thời Edo (năm 1603 đến 1868), giấm được dùng thay cho men lacto để làm chua gạo. Trong thời hiện đại, đây là một hình thức ban đầu của thức ăn nhanh gắn liền với văn hóa Nhật Bản.

Các bản gốc của sushi, ngày nay được gọi là narezushi (lên men sushi), được phát triển đầu tiên ở Đông Nam Á và lan rộng đến miền nam Trung Quốc trước khi đến Nhật Bản vào khoảng thế kỷ thứ 8. Narezushi được làm bằng cá đã làm sạch ruột, ủ trong gạo lên men lacto truyền thống suốt nhiều tháng để bảo quản. Quá trình lên men của gạo giữ cá không bị hư. Sau đó, người ta bỏ gạo lên men, chỉ ăn cá. Phương thức làm sushi rất xa xưa này đã trở thành nguồn cung cấp protein quan trọng cho người Nhật.

Người Nhật thích dùng cá với cơm, gọi là namanare hoặc namanari (lên men bán phần). Trong thời Muromachi, namanare là dạng phổ biến nhất của sushi. Đó một phần là cá sống được bọc trong cơm, dùng tươi, trước khi nó thay đổi hương vị. Dạng này không còn là phương pháp bảo quản cá mà là một món mới trong ẩm thực Nhật Bản.

Trong thời kỳ Edo, một loại thứ ba của sushi đã được giới thiệu, Haya-zushi (sushi nhanh). Haya-zushi đã được kết hợp để cơm và cá có thể được dùng cùng lúc, và món ăn trở thành món độc nhất biểu tượng cho văn hóa Nhật Bản. Đây là lần đầu tiên mà cơm không qua quá trình lên men. Giờ đây cơm được trộn với giấm, cá, rau quả và thêm thực phẩm khô. Loại sushi này hiện vẫn rất phổ biến, mỗi vùng miền lại dùng sản vật địa phương để biến tấu ra nhiều loại sushi, và được truyền lại qua nhiều thế hệ.

Khi Tokyo vẫn còn được gọi là Edo trong những năm đầu thế kỷ 19, các quầy hàng thực phẩm di động với những người bán hàng rong trở nên phổ biến. Trong khoảng thời gian này sushi nigiri đã được giới thiệu, nó gồm một nén cơm nhỏ thuôn dài, với một lát cá phủ lên trên. Sau trận động đất Great Kanto năm 1923, nhiều đầu bếp sushi nigiri đã rời Edo và đi đến khắp các vùng khác, họ đã phổ biến các món ăn đến mọi nơi trong nước Nhật.

Ngày nay, món sushi được thế giới biết đến như là "sushi" (zushi nigiri) là một thức ăn nhanh được phát minh bởi Hanaya Yohei (1799-1858) tại Tokyo. Người dân Tokyo giờ sống gấp gáp cũng như hơn một trăm năm trước đây. Loại sushi phát minh bởi Hanaya không được lên men, có thể ăn bằng ngón tay hoặc đũa. Đó là hình thức ban đầu của thức ăn nhanh, thường được dùng ở nơi công cộng hay tại nhà hát.

Funazushi

Funazushi là một loại hiếm của narezushi, vẫn được làm gần hồ Biwa, quận Shiga. Mười tám thế hệ của gia đình Kitamura đã làm ra các món ăn tại Kitashina kể từ năm 1619.

Funa tươi là cách đánh vảy, rút ruột qua mang để giữ cho cơ thể (và trứng) cá còn nguyên vẹn. Con cá này sau đó được đóng gói với muối và giữ trong một năm, sau đó hàng năm được bọc lại trong cơm, trong suốt bốn năm. Kết quả là món ăn lên men, có thể được ăn bằng cách thái lát hoặc dùng kèm với các món ăn khác.

Các funazushi thật được làm từ một loài đặc biệt được gọi là nigorobuna (Carassius auratus grandoculis) duy nhất trong hồ. Vì thế, khá sai lầm khi nói "cá chép cheo" được sử dụng, cũng như bất kỳ loại cá chép Funa xưa nào trong chi (hoặc các loài châu Âu) đều có thể được ngẫu nhiên sử dụng. Đúng là do giảm khai thác trong những năm gần đây, các loài bản địa nào đó đang bắt đầu được thay thế.

Xuất hiện ở phương Tây

Từ điển tiếng Anh Oxford đã đề cập đến sushi sớm nhất bằng văn bản trong một cuốn sách năm 1893, Nội thất Nhật Bản, trong đó viết rằng "Người bản xứ đã phục vụ chúng tôi trà và sushi hoặc cơm kẹp".  Tuy nhiên, cũng có một bài viết về sushi trong từ điển Nhật-Anh từ năm 1873, và một bài viết năm 1879 về món ăn Nhật Bản trên tạp chí Ghi chú và Thắc mắc.

Một báo cáo đã ghi nhận sushi được dùng tại Anh trong dịp Hoàng tử Akihito (sinh năm 1933) đến thăm Nữ hoàng Elizabeth II trong thời gian bà đăng quang tháng 5/1953. Ở Mỹ vào tháng 9/1953, Hoàng tử Akihito đã được phục vụ món sushi tại Đại sứ quán Nhật Bản tại Washington, được tổ chức bởi Đại sứ Eikichi Araki (1891-1959).

Sushi lần đầu tiên được giới thiệu tại Hoa Kỳ vào giữa thập niên 1960, có thể là tại nhà hàng Kawafuku trong khu phố Little Tokyo của Los Angeles. Các cuộn California đã được phát minh ra ở Los Angeles, bằng cách thay thế một lát bơ cho toro (cá ngừ béo) theo mùa trong cuộn maki truyền thống.

Sushi ở Nhật Bản

Các tài liệu tham khảo sớm nhất về sushi  ở Nhật Bản xuất hiện tại 718 trong Bộ luật Yoro (Yoro-Ritsuryo). Trong đó, có món được gọi là zakonosushi hoặc zatsunosushi. Tuy nhiên, không cách nào biết được đây là sushi gì hoặc thậm chí phát âm nó ra sao. Đến thế kỷ thứ 9 và 10 nó chính thức được gọi là "sushi". Và nó cũng tương tự như Narezushi ngày nay.

Trong gần 800 năm tiếp theo, cho đến đầu thế kỷ 19, sushi từ từ thay đổi và ẩm thực Nhật Bản cũng thay đổi. Người Nhật bắt đầu ăn ba bữa một ngày, gạo được nấu thay vì hấp, và quan trọng nhất là giấm gạo được phát minh. Trong khi sushi tiếp tục được sản xuất bằng quá trình lên men cá với cơm, thời gian lên men giảm dần và gạo dùng để lên men bắt đầu được ăn cùng với cá. Trong thời Muromachi, quá trình sản xuất Oshizushi đã dần dần phát triển, người ta không lên men nữa, giấm được sử dụng thay thế. Sushi cũng bắt đầu được bán trong các công viên, gần các nhà hát như một loại Bento.

Có ba nhà hàng sushi nổi tiếng ở Edo, Matsunozushi, Yoheizushi, và Kenukizushi, nhưng có hàng ngàn nhà hàng sushi khác. Chúng được thành lập trong vòng hai mươi năm đầu thế kỷ 19. Nigirizushi là một cú hit và ngay lập tức và nó lây lan cả Edo như trận cháy rừng. Trong cuốn sách Morisadamanko xuất bản năm 1852, tác giả viết rằng một mỗi hecta (10,000 mét vuông) đất của Edo có 1 hoặc 2 nhà hàng sushi.

Nigirizushi ban đầu không giống với ngày nay. Thịt cá được ướp trong nước sốt đậu nành, hoặc giấm hoặc nhiều muối như vậy, nên khi ăn không có cần phải chấm nước tương đậu nành. Một số loài cá được nấu chín trước khi dùng chế biến sushi, bởi vì thời đó chưa có tủ lạnh. Mỗi phần sushi cũng lớn hơn, kích thước gần gấp đôi miếng sushi ngày nay.

Sự xuất hiện của tủ lạnh hiện đại đã cho phép làm sushi cá tươi đạt mức độ tiêu dùng tốt hơn bao giờ hết, và đến cuối thế kẻ 20, sushi đã phổ biến trên toàn toàn thế giới.