Using a Legendre transformation, we compute the unconstrained Hamiltonian of a spinning test-particle in a curved spacetime at linear order in the particle spin. The equations of motion of this unconstrained Hamiltonian coincide with the Mathisson-Papapetrou-Pirani equations. We then use the formalism of Dirac brackets to derive the constrained Hamiltonian and the corresponding phase-space algebra in the Newton-Wigner spin supplementary condition (SSC), suitably generalized to curved spacetime, and find that the phase-space algebra (q,p,S) is canonical at linear order in the particle spin. We provide explicit expressions for this Hamiltonian in a spherically symmetric spacetime, both in isotropic and spherical coordinates, and in the Kerr spacetime in Boyer-Lindquist coordinates. Furthermore, we find that our Hamiltonian, when expanded in Post-Newtonian (PN) orders, agrees with the Arnowitt-Deser-Misner (ADM) canonical Hamiltonian computed in PN theory in the test-particle limit. Notably, we recover the known spin-orbit couplings through 2.5PN order and the spin-spin couplings of type S_Kerr S (and S_Kerr^2) through 3PN order, S_Kerr being the spin of the Kerr spacetime. Our method allows one to compute the PN Hamiltonian at any order, in the test-particle limit and at linear order in the particle spin. As an application we compute it at 3.5PN order.