We examine constraints from Big Bang nucleosynthesis on type II Randall-Sundrum brane cosmologies with both a dark radiation component and a quadratic term that depends on the 5-dimensional Planck mass, M_5. Using limits on the abundances of deuterium and helium-4, we calculate the allowed region in the M_5-dark radiation plane and derive the precise BBN bound on M_5 alone with no dark radiation: M_5 > 13 TeV.