The remarkable tunability of 2D carbon structures combined with their non-toxicity renders them interesting candidates for thermoelectric applications. Despite some limitations related to their high thermal conductivity and low Seebeck coefficients, several other unique properties of the graphene-like structures could out-weight these weaknesses in some applications. In this study, hybrid structures of alumina ceramics and graphene encapsulated alumina nanofibers are processed by spark plasma sintering to exploit advantages of thermoelectric properties of graphene and high stiffness of alumina. The paper focuses on thermal and electronic transport properties of the systems with varying content of nanofillers (1–25 wt.%) and demonstrates an increase of the Seebeck coefficient and a reduction of the thermal conductivity with an increase in filler content. As a result, the highest thermoelectric figure of merit is achieved in a sample with 25 wt.% of the fillers corresponding to ~3 wt.% of graphene content. The graphene encapsulated nanofibrous fillers, thus, show promising potential for thermoelectric material designs by tuning their properties via carrier density modification and Fermi engineering through doping.