Some of the most vivid colors in the animal kingdom are created not by pigments, but by wavelength-selective scattering of light from nanostructures. Here we investigate quasi-ordered nanostructures of avian feather barbs which produce vivid non-iridescent colors. These β-keratin and air nanostructures are found in two basic morphologies: tortuous channels and amorphous packings of spheres. Each class of nanostructure is isotropic and has a pronounced characteristic length scale of variation in composition. These local structural correlations lead to strong backscattering over a narrow range of optical frequencies and little variation with angle of incidence. Such optical properties play important roles in social and sexual communication. To be effective, birds need to precisely control the development of these nanoscale structures, yet little is known about how they grow. We hypothesize that multiple lineages of birds have convergently evolved to exploit phase separation and kinetic arrest to self-assemble spongy color-producing nanostructures in feather barbs. Observed avian nanostructures are strikingly similar to those self-assembled during the phase separation of fluid mixtures; the channel and sphere morphologies are characteristic of phase separation by spinodal decomposition and nucleation and growth, respectively. These unstable structures are locked-in by the kinetic arrest of the β-keratin matrix, likely through the entanglement or cross-linking of supermolecular β-keratin fibers. Using the power of self-assembly, birds can robustly realize a diverse range of nanoscopic morphologies with relatively small physical and chemical changes during feather development.