A topological insulator (TI) interfaced with a magnetic insulator (MI) may host an anomalous Hall effect (AHE), a quantum AHE, and a topological Hall effect (THE). Recent studies, however, suggest that coexisting magnetic phases in TI/MI heterostructures may result in an AHE-associated response that resembles a THE but in fact is not. This article reports a genuine THE in a TI/MI structure that has only one magnetic phase. The structure shows a THE in the temperature range of T=2-3 K and an AHE at T=80-300 K. Over T=3-80 K, the two effects coexist but show opposite temperature dependencies. Control measurements, calculations, and simulations together suggest that the observed THE originates from skyrmions, rather than the coexistence of two AHE responses. The skyrmions are formed due to an interfacial DMI interaction. The DMI strength estimated is substantially higher than that in heavy metal-based systems.