In a universe of the Randall-Sundrum type, black holes are unstable and emit gravitational modes in the extra dimension. This leads to dramatically shortened lifetimes of astrophysical black holes and to an observable change of the orbital period of black-hole binaries. I obtain an upper limit on the rate of change of the orbital period of the binary XTE J1118+480 and constrain the asymptotic curvature radius of the extra dimension to a value that is of the same order as the constraints from other astrophysical sources. A unique property of XTE J1118+480 is that the expected rate of change of the orbital period due to magnetic braking alone is so large that only one additional measurement of the orbital period would lead to the first detection of orbital evolution of a black-hole binary and impose the tightest constraint to date on the size of one extra dimension of the order of 35 microns.