Two new sesquiterpenes, 10beta-methoxymuurolan-4-en-3-one (1) and 10alpha-methoxycadinan-4-en-3-one (2), were isolated from the root bark of Zanthoxylum ailanthoides. The structures of 1 and 2 were elucidated from spectroscopic data. Sixty-seven compounds obtained from the root bark of the same plant were evaluated for inhibition of HIV replication in H9 lymphocyte cells, and 14 compounds demonstrated significant activity. Among them, decarine, gamma-fagarine, and (+)-tembamide were the most potent anti-HIV compounds, with EC50 values of <0.1 microg/mL and TI values of >226, >231, and >215, respectively.