Starting with a palette of four colors, a 4-color cube is one where each face is colored with exactly one color and each color appears on some face–there are a total of sixtyeight distinct varieties of 4-color cubes. In the 4-Color Cube puzzle, one is given a set of 4-color cubes and tries to arrange a subset into a larger n×n×n 4-color cube. To solve this puzzle, it is sufficient to fill in the large cube’s n-frame, its corners and edges. For each n we determine a minimal value, fr(n), so that given any arbitrary collection of fr(n) 4-color cubes, there is always a subset which can be used to build an n-frame. In particular, we are able to show that for n ≥ 3, fr(n) = 12n − 16, the smallest possible number. In addition, we describe a set of ten distinct 4-color cubes from which it is possible to build 2 × 2 × 2 frames modeled on all sixty-eight color cube varieties and conclude that this is the smallest size of such a set.