Bimetallic clusters have aroused increased attention because of the ability to tune their own properties by changing size, shape, and doping. In present work, a structural search of the global minimum for divalent bimetal Be2Mgn (n = 1-20) clusters are performed by utilizing CALYPSO structural searching method with subsequent DFT optimization. We investigate the evolution of geometries, electronic properties, and nature of bonding from small to medium-sized clusters. It is found that the structural transition from hollow 3D structures to filled cage-like frameworks emerges at n = 10 for Be2Mgn clusters, which is obviously earlier than that of Mgn clusters. The Be atoms prefer the surface sites in small cluster size, then one Be atom tend to embed itself inside the magnesium motif. At the number of Mg larger than eighteen, two Be atoms have been completely encapsulated by caged magnesium frameworks. In all Be2Mgn clusters, the partial charge transfer from Mg to Be takes place. An increase in the occupations of the Be-2p and Mg-3p orbitals reveals the increasing metallic behavior of Be2Mgn clusters. The analysis of stability shows that the cluster stability can be enhanced by Be atoms doping and the Be2Mg8 cluster possesses robust stability across the cluster size range of n = 1-20. There is s-p hybridization between the Be and Mg atoms leading to stronger Be-Mg bonds in Be2Mg8 cluster. This finding is supported by the multi-center bonds and Mayer bond order analysis.