  Using a recent, novel Hamiltonian formulation of the gravitational
interaction of spinning binaries, we extend the Effective One Body (EOB)
description of the dynamics of two spinning black holes to next-to-leading
order (NLO) in the spin-orbit interaction. The spin-dependent EOB Hamiltonian
is constructed from four main ingredients: (i) a transformation between the
``effective'' Hamiltonian and the ``real'' one, (ii) a generalized effective
Hamilton-Jacobi equation involving higher powers of the momenta, (iii) a
Kerr-type effective metric (with Pad\'e-resummed coefficients) which depends on
the choice of some basic ``effective spin vector'' $\bf{S}_{\rm eff}$, and
which is deformed by comparable-mass effects, and (iv) an additional effective
spin-orbit interaction term involving another spin vector $\bsigma$. As a first
application of the new, NLO spin-dependent EOB Hamiltonian, we compute the
binding energy of circular orbits (for parallel spins) as a function of the
orbital frequency, and of the spin parameters. We also study the
characteristics of the last stable circular orbit: binding energy, orbital
frequency, and the corresponding dimensionless spin parameter $\hat{a}_{\rm
LSO}\equiv c J_{\rm LSO}/\boldsymbol(G(H_{\rm LSO}/c^2)^2\boldsymbol)$. We find
that the inclusion of NLO spin-orbit terms has a significant ``moderating''
effect on the dynamical characteristics of the circular orbits for large and
parallel spins.
