Brillouin measurements of the dispersion relations of surface acoustic- and optical-like waves along Γ-M and Γ-X symmetry directions in a two-dimensional bicomponent nanostructured crystal are reported. The sample, in the form of a periodic chessboard array of alternating Permalloy and cobalt square dots on a SiO /Si substrate, was fabricated using high-resolution electron-beam lithographic, sputtering, etching, and lift-off techniques. The measured phononic band structures exhibit diverse features, such as a partial hybridization bandgap and unusual surface optical-like phonon branches, where there are out-of-phase vibrational characteristics between nearest-neighbor dots. Numerical simulations, based on the finite element analysis, reproduced the experimental dispersion relations. © 2012 American Institute of Physics.