Monte Carlo simulated annealing strategies, carried out on four different potential energy surfaces, are applied to benzene-cyclohexane clusters, BCn, n=3-7, 12, to identify low-energy isomers and to trace the evolution of structures as a function of cluster size. Initial structures are first heated to ensure randomization, and subsequent annealing yields optimized rigid, low-energy clusters. Five major structural isomers are identified for BC3: one assumes the form of a symmetric, modified sandwich; the remaining four lack general symmetry, assuming distorted tetrahedral arrangements. For BC4 and larger clusters, the number of low-temperature isomers is large. It is, nevertheless, feasible to classify isomers into groups based on structural similarities. The evolution of BCn structures as a function of cluster size is observed to follow one of two primary paths: The first maximizes benzene-cyclohexane interactions and places benzene in or near the BCn cluster center; the competing path maximizes cyclohexane-cyclohexane interactions and distances benzene from the cluster's center of mass. Results for BC3 and BC4 are discussed with reference to experimental results and models previously applied to interpret benzene-argon cluster spectra.