The area of what now is Ussuriysk was settled by Yulou Mohe tribes. From the mid-9th century, it became Solbin-bu of the Balhae Kingdom. It is then populated by the Dōnghǎi Jurchens, under control of Liao dynasty. The city then become capital of Jīn Dynasty's Sùpín circuit (速頻路). Then it went under control of Yuan, Ming and Qing dynasties respectively.
In 1866, the settlement of Nikolskoye (Нико́льское) was founded on the area of today's Ussuriysk, named after Saint Nicholas. Due to its advantageous geographic location at the crossing of the transportation lines, the village experienced rapid growth during the 1870s, turning into a trade center. Its role increased after the railroad connecting Khabarovsk and Vladivostok (now a part of the Trans-Siberian Railway) was built, and in 1898 it was granted town status and renamed Nikolsk-Ussuriysky (Нико́льск-Уссури́йский).
By the beginning of the 20th century the town's population totaled 15,000 people, and the annual turnover of its trade enterprises was equal to three million rubles. After the Russo-Japanese War of 1904-1905, Nikolsk-Ussuriysky became one of the most important commercial and economic centers of the Russian Far East. In 1913, the city ranked fourth after Vladivostok, Blagoveshchensk, and Khabarovsk in terms of population. Enterprises were established processing agricultural products such as mills, dairies, soap-boiling plants, and tanneries, as well as macaroni and sausage factories and breweries. Brick factories, quarries, and saw-mills were also built.
The central part of the city began to be built up with two- and three-story masonry buildings. In 1914, there were fourteen educational institutions, a theater, a circus, and three movie-theaters in Nikolsk-Ussuriysky.
After the October Revolution of 1917, the city's economy experienced rapid growth. The city specialized in processing agricultural products. The name of the city was changed to Voroshilov in 1935 after Kliment Voroshilov. With Nikita Khrushchev's ascent to power after Stalin's death the city's name was changed to Ussuriysk after the nearby Ussuri River in 1957.