We consider charged black holes in Einstein-Gauss-Bonnet Gravity with Lifshitz boundary conditions. We find that this class of models can reproduce the anomalous specific heat of condensed matter systems exhibiting non-Fermi-liquid behaviour at low temperatures. We find that the temperature dependence of the Sommerfeld ratio is sensitive to the choice of Gauss-Bonnet coupling parameter for a given value of the Lifshitz scaling parameter. We propose that this class of models is dual to a class of models of non-Fermi-liquid systems proposed by Castro-Neto et.al.