Avdyushko was born to a father who worked as a weight inspector in the Kiyevsky Rail Terminal and to a housewife mother, who also raised one older daughter.

Avdyushko continued to play supporting characters during the following years, in pictures such as Cossacks of the Kuban and Hostile Whirlwinds.

[2] In 1957, Avdyushko was cast for the leading role in Mikhail Schweitzer's Tight Knot, adapted from a story by Vladimir Tendryakov.

[3] The actor starred in many films during the 1960s and early 1970s, and performed in fifty until the end of his career, including the 1961 Biennale Jury Prize winning Peace to Him Who Enters and the 1964 The Alive and the Dead, based on Konstantin Simonov's novel.

He also worked with foreign studios, mainly East Germany's DEFA: He played in Konrad Wolf's 1958 Sun Seekers and in Frank Beyer's 1963 Naked among Wolves.