In this paper, priority-aware scheduling to the coexistence of multiple wireless body area networks (WBANs) is addressed. The scheduling is formulated as a nonlinear optimization problem where the objective is to maximize system throughput while guaranteeing the priorities among WBANs. To overcome the inherent complexity issue, a new method, called recursive decomposition algorithm (RDA), is proposed to solve the original nonlinear problem by decomposing it into several linear subproblems. Each subproblem is then solved by a column generation method in order to avoid the large number of variables. Since the pricing problem in the column generation method is a 0–1 integer programming which is known to be NP-complete, a heuristic weight-greedy algorithm with a much lower time complexity is proposed. The simulation results show that the proposed RDA can effectively guarantee the priorities among WBANs and can obtain near-optimal throughput performance even in the extremely high user density region.