Recent discoveries of super-massive black holes at high redshifts indicate a possible tension with the standard Lambda CDM paradigm of early universe cosmology which has difficulties in explaining the origin of the required nonlinear compact seeds which trigger the formation of these super-massive black holes. Here we show that cosmic string loops which result from a scaling solution of strings formed during a phase transition in the very early universe lead to an additional source of compact seeds. The number density of string-induced seeds dominates at high redshifts and can help trigger the formation of the observed super-massive black holes.