An octree partition of unity method (OctPUM) with enrichments for multiscale modeling of heterogeneous media. In this paper we present some enrichment techniques for the modeling of heterogeneous media in the presence of singularities such as cracks which overcome long-standing problems associated with the assumption of local periodicity in traditional asymptotic homogenization methods. An octree partition of unity method (OctPUM) is developed to solve the macroscopic problem. In this technique the geometry is discretized using hierarchical data structures known as quadtrees and octrees in two- and three-dimensions, respectively and the approximation functions, generated using the partition of unity approach, are compactly supported on n-dimensional cubes. OctPUM is in-between finite elements and meshfree methods in character and is computationally more efficient than pure meshfree techniques. Solutions near crack tips may be obtained without excessive local refinements using localized enrichment functions. In order to compute the microscopic fields near the crack edge within the macroscale computations, a structural enrichment-based homogenization method is introduced in which the approximation space of the OctPUM at the macroscopic scale is enriched by functions generated at the microscopic scale using the asymptotic homogenization technique. Several example problems in one- and two-dimensional analysis, including one involving realistic microstructures, are solved to demonstrate the effectiveness of the enrichment strategies.