NK Orijent was founded in 1919 in Sušak, eastern part of the present day city of Rijeka. At the time, Sušak was predominantly Croatian, while Fiume, the western part of the city, was predominantly Italian. According to the legend, during his time on journey to the United States, one of the club's founders saw a ship named Orient in the New York Harbor. After he came back, he suggested the new club to be named Orient, a suggestion which was later accepted. As regimes changed, Orijent was often forced to change its name. At various stages of its history the club was known as Jedinstvo, Primorac, Primorje and Budućnost. Finally, from 1953 onwards, the club carries the original name: Orijent. Although Orijent spent most of its history in lower tiers of Yugoslav and Croatian football, it was and still is popular among Sušak's population.
The club's greatest success came in 1969 when they were the champions of Yugoslav Second League's Division West but were unable to win promotion through playoff. Orijent and city rivals Rijeka contested numerous derbies during the early 1970s. Other notable successes were quarter-finals of Yugoslav Cup in 1980–81 and 1982–83. Orijent played top tier football only once, during the season 1996–97 when they finished 14th and were relegated.