In Ukraine after World War II, Spartak sports teams represented a regional government.

That season of republican competitions conditionally is called as the "Soviet Third Group" (Tretya Gruppa).

Spartak placed only second in its group behind Bilshovyk Zaporizhia, but were admitted next year to the All-Union competitions, nonetheless.

The club was formed in 1961 at the Kherson Semiconductor Factory as Mayak (English: Lighthouse).

Due to reforms in Soviet football, the division where Stroitel played was demoted the third tier.

The very same year another Lokomotyv Kherson also played in the newly formed competitions among physical fitness clubs.

In 1968, the Kherson club was promoted and for couple of seasons played at Class A until 1970 reform when it was admitted to the newly formed Soviet Second League (again as the third tier).