The original type of sushi was first developed in Southeast Asia long, long time ago, and spread to south China,
なれずし
then introduced to Japan by the beginning of the 8th century. It was called 馴れ鮨 (or 熟れ鮨 / なれずし)  [narezushi]. 
なれずし2
Narezushi is fish salted and wrapped in fermented rice for more than 6 months for preservation.
なれずし3
The fermented rice was discarded and fish was the ONLY part consumed.
It’s still available in Japan as local food.
なれずし4
There are various types of fish cooked for narezushi.
なれずし2なれずし1

Japanese people wanted to eat rice as well. Therefore, a new type of sushi, called 生馴れ (or 生熟れ / なまなれ) [namanare], was born  during Muromachi Period (1336–1573). The fish was stored in rice for a shorter period and eaten with the rice.
なまなれ
鯖なまなれ 
鯖なれずし (mackerel)

During Enpō Period (1673-1681), 押し鮨(おしずし)[oshizushi] became popular. It’s formed using a wooden mold. Instead of fermented rice, vinegar was added.
押しずし
It is now a specialty of Osaka and some other areas.
押しずし2

During Bunsei Period (1818-1830), it is maintained that 握り鮨(にぎりずし)[nigiri zushi] was invented by華屋与兵衛(はなやよへい)[Hanaya Yohē] in Tokyo area. It was available from vendors at that time. Nigiri was an early form of fast food that could be eaten in public or in the theatres.
にぎり 屋台
握りずし屋台握りずし屋台2

As seen above, sushi has a long history.
年表
It is said that sushi became popular in the Edo Period due to a great branding.
Since people in old Tokyo were superstitious, sushi retailer changed the character of sushi “” meaning “yummy fish ( + )” to “寿司” symbolising “managing happiness”.


ブランディング
This successful branding gained a great popularity of sushi.
ブランディング2