La Historia de Enrique, fi de Oliva es una de esas obras narrativas medievales que nadie sabe muy bien dentro de qué género se ha de encuadrar. Desde un principio se la ha venido considerando como un libro de caballerías, y quizá haya que dejarla dentro de este grupo genérico, ya que como tal aparece en el Quijote (I, XVI), aunque de manera velada puesto que no se menciona al héroe sino al traidor Tomillas:
¡Bien haya mil veces el autor de Tablante de Ricamonte, y aquel del otro libro donde se cuentan los hechos del conde Tomillas, y con qué puntualidad lo describen todo!
Y como libro de caballerías la han considerado algunos de los más recientes investigadores que se han acercado a esta obra [Campbell, 1988: 3]; [Griffin, 1990]. La mayor objección para no aceptar su adscripción como un libro de caballerías es que no es una obra cuyo final permita, o dé pie, a futuras continuaciones. La Historia de Enrique, fi de Oliva es un cuento de final feliz: tras rehabilitar la honra de su madre, sus padres se vuelven a casar y él vuelve con su esposa con la que tiene un heredero. En la actualidad se ha querido considerarla como un romance, en el sentido inglés de la palabra [Gómez Redondo, 1993].
Éste es el caso de Fernando Gómez Redondo, para quien la Historia de Enrique, fi de Oliva es un romance de materia literaria [1991: 170-171] y más especificamente un romance del ciclo carolingio ya que la madre del héroe es hermana del rey Pepino de Francia.
Las recientes investigaciones de Víctor Infantes no encuadran esta narración, y otras semejantes, como un género literario sino editorial [Infantes, 1989], aunque con posterioridad se refiere a la Historia de Enrique como «narración caballeresca breve»18 [Infantes, 1991]. Este género editorial, de relatos caballerescos breves, textos de fácil lectura, cierta brevedad, en el que se muestra un mundo idealizado en el que los personajes se encuentran en grado superlativo: los buenos son buenísimos y los malos malísimos, se refiere a los impresos que se inician en la época incunable y cuyo auge se da a lo largo del siglo xvi. Así, de la Historia de Enrique, como se verá a continuación, se imprimieron ocho ediciones de otras obras encuadradas por Infantes dentro de este género, como es el caso de la Historia del emperador Carlomagno y los doce pares de Francia, se imprimieron doce ediciones en el siglo xvi, diecinueve en el xvii, treinta y ocho en el xviii y treinta y nueve en el xix, o la Crónica del conde Fernán González con veintitrés ediciones en el siglo xvi, tres en el xvii, diez en el xviii y cinco en el xix.19 Y así los considera José Manuel Lucía en su reciente catálogo de los Libros de caballerías castellanos en las bibliotecas públicas de París; en él incluye un apéndice títulado «Catálogo descriptivo de las historias caballerescas conservadas en la bibliotecas públicas de París» (pp. 266-302) en el que recoge sendos testimonios de la Historia de Enrique, fi de Oliva (n.os XVI-XVIII, pp. 281-282).