Historically, speakers have resolved this opposition by assimilating the place of articulation of the velar consonant to that of the front vowel, thereby palatalizing it.
Compare: Even though it is commonly stated in the literature that the result of first palatalization were consonants */č/, */ž/, */š/, there is no certain evidence that that process was indeed finished by 600 CE.
However, that change is in fact Common Slavic (post-Proto-Slavic), which is obvious e.g. from the adaption of Romance toponyms in the Adriatic, to which Slavs subsequently spread well after the 5th century, when first regressive palatalization is usually dated.
With that in mind, consonants */č/ and */ž/, which are usually reconstructed in the phonemic inventory of Proto-Slavic in the literature, were likely to be just phonologically predictable allophones of */k/, and */g/, and have remained such until conditions were met after the 600 CE for their appearance behind back vowels as well.
The first palatalization gave the same results in all Slavic languages, which shows that it probably took place before the migration of Slavs into their historical settlements, and that means probably before 500 CE.