Podillya started out as a subsection of the Soviet Dynamo athletic franchise in 1948, under the name of Dynamo, of course. The team was renamed after the historical Ukrainian region where it played its home games, Podillya. After Ukraine gained independence in 1991, Podillya was placed in the Ukrainian First League from the very first season. Podillya finished the year in fourth place out of fourteen teams under the management of Hrynevych.
It was renamed as "Nord-Am Ltd.- Podillya" in the 1993 season after its sponsor, Nord-Am Ltd. During that season Podillya hired Yuriy Avanesov as its manager. Until club's relegation in 1998 to the Druha Liha the team was placing inconsistently in the middle of the tournament table. As a result of the relegation Avanesov was fired and replaced by Kvartsyaniy. He managed the team until September 1997. The team finished the first half of the next season in second place after the return of Avanesov. The year that he returned the team finished first in the Druha Liha and was promoted to the Persha Liha again. They started the 1998/99 season in the Persha Liha however they finished in 16th out of 20 and were relegated again.
They started the 1999/2000 season in Druha Liha A and finished in 2nd place, one stop away from promotion. The 2000/01 season was another year in the Ukrainian Second League where they finished in 6th place in Druha Liha B. The 2001/02 season was another shortcoming season for Podillya when they finished in 3rd with 27 wins, but still one spot away from promotion. Podillya finished the 2002/03 season in 3rd place in Druha Liha A. The 2003/04 season was another 2nd place finish in Druha Liha A, but still one spot from promotion. Podillya started the 2004/05 season in the Ukrainian First League after finishing second the year before. Despite not being in position for promotion Podillya merged with FC Krasyliv.
^The PFL deducted 12 points for various infringements during the course of the season
^After the season, the club which was administered in Krasyliv, was dissolved because of lack of finances. A new club FC Podillya-Khmelnytskyi had been formed and entered the Druha Liha Group A competition