  We study holographic conformal anomalies and the corresponding $a$-theorem
for Einstein gravity extended with Horndeski terms that involve up to and
including linear curvature tensors. We focus on our discussion in $D=5$ bulk
dimensions. For the generic Horndeski coupling, the $a$-charge is the same as
that in Einstein gravity, but the inclusion of the Horndeski term violates the
$a$-theorem. However, there exists a critical point of the Horndeski coupling,
for which the theory admits nearly AdS spacetimes with non-vanishing Horndeski
scalar. The full AdS isometry is broken down by the logarithmic scalar hair to
the Poincar\'e group plus the scale invariance. We find that in this case the
$a$-charge depends on the AdS radius $\ell$ and the integration constant
$\chi_s$ of the Horndeski scalar. In addition, we find that two new central
charges emerge, that are absent in gravities with minimally-coupled matter. We
call them $b$-charges. These $b$-charges also depend on $\ell$ and $\chi_s$. We
construct an $a$-function for fixed $\ell$ but with the running Horndeski
scalar $\chi$ replacing the constant $\chi_s$, and establish the holographic
$a$-theorem using the null energy condition in the bulk. Furthermore, we find
that there exist analogous monotonous $b$-functions as well. We also obtain the
$a$-charge and the $a$-theorem in general odd bulk dimensions.
