Coupling beam angle optimization with dose optimization in intensity-modulated radiation therapy (IMRT) increases the size and complexity of an already large-scale combinatorial optimization problem. We have developed a novel algorithm, nested partitions (NP), that is capable of finding suitable beam angle sets by guiding the dose optimization process. NP is a metaheuristic that is flexible enough to guide the search of a heuristic or deterministic dose optimization algorithm. The NP method adaptively samples from the entire feasible region, or search space, and coordinates the sampling effort with a systematic partitioning of the feasible region at successive iterations, concentrating the search in promising subsets. We used a 'warm-start' approach by initiating NP with beam angle samples derived from an integer programming (IP) model. In this study, we describe our implementation of the NP framework with a commercial optimization algorithm. We compared the NP framework with equi-spaced beam angle selection, the IP method, greedy heuristic and random sampling heuristic methods. The results of the NP approach were evaluated using two clinical cases (head and neck and whole pelvis) involving the primary tumor and nodal volumes. Our results show that NP produces better quality solutions than the alternative considered methods.