Por su estrecha gran antigüedad y su relación con la fundación de la ciudad y la catedral de Compostela, la iglesia de San Fiz de Solovio está envuelta en la leyenda. Aparece así citada en muchos itinerarios de peregrinos de otros tiempos, como Leo de Rozmital (1465-1467) quien dejo de ella: “Fuera, antes de la ciudad, hay una pequeña iglesia que se cree que fue construida por Santiago y que él vivió allí la mayor parte del tiempo que predicó en Galicia”.

La leyenda narra que fue la primera iglesia de Compostela, en origen un pequeño eremitorio donde a comienzos del siglo IX vivió el anacoreta llamado Paio, uno de tantos religiosos que durante los primeros siglos de cristianización de Galicia se refugiaron en parajes hermosos y aislados para dedicarse a la contemplación y hacer penitencia. Según la tradición todo ocurrió hacia el año 820, durante reinado de Alfonso II (791-842) y siendo obispo de Iria Flavia Teodomiro (819?-847). El eremita Paio se hallaba una noche en oración cuando empezó a ver luces que señalaban algún lugar no muy lejano, guiado por ella y cantos de coros angelicales caminó hasta encontrar el túmulo donde se hallaban los restos del Apóstol.

Si pasamos de la leyenda a la historia, sabemos que la iglesia actual, situada junto al popular mercado de Santiago, fue fundada antes del siglo IX tomando el nombre de Lobio de una aldea cercana a Compostela. En tiempos del rey Alfonso III (866-910) los clérigos de esta iglesia pasaron a formar parte de la comunidad de la catedral de Santiago, a la que siguieron perteneciendo durante siglos. Sabemos también que la arquitectura de la iglesia fue seriamente dañada por las invasiones y ataques musulmanes, por lo que hacia el año 1122, durante el obispado de Gelmírez (1100-1140), verdadero mecenas e impulsor de la ciudad y la peregrinación a Compostela, tuvo que ser reedificada.

A comienzos del siglo XIV la iglesia románica fue dotada del pórtico actual, con un hermoso relieve sobre su tímpano en el que aparece representada la Epifanía o adoración de los Reyes, trabajo en granito cuya ejecución ha sido documentada en 1316 y atribuida al maestro F. Paris. El alto relieve no es el único de Compostela sobre este tema, pues ya existía una representación de la escena en el tímpano de la portada de acceso a la famosa capilla de la Corticela, en la catedral, pero posee un especial interés por conservar gran parte de la policromía original. La arquitectura se completó siglos después con una torre barroca, obra del arquitecto compostelano Simón Rodríguez (1679-1751).

El peregrino que tenga oportunidad debe visitar su interior, con el magnífico sepulcro del cardenal Lopo González de Carballido y, presidiendo su retablo, la popular imagen de la Virgen de los Milagros.