This paper describes our experiences developing high- performance code for astrophysical N-body simulations. Recent N-body methods are based on an adaptive tree structure. The tree must be built and maintained across physically distributed memory; moreover, the commu- nication requirements are irregular and adaptive. To- gether with the need to balance the computational work-load among processors, these issues pose interest- ing challenges and tradeoffs for high-performance im- plementation. Our implementation was guided by the need to keep solutions simple and general. We use a technique for im- plicitly representing a dynamic global tree across multi- ple processors which substantially reduces the program- ming complexity as well as the performance overheads of distributed memory architectures. The contributions include methods to vectorize the computation and min- imize communication time which are theoretically and experimentally justified. The code has been tested by varying the number and distribution of bodies on different configurations of the Connection Machine CM-5. The overall performance on instances with 10 million bodies is typically over 30% of the peak machine rate. Preliminary timings compare favorably with other approaches.