A connected dominating set (CDS) is used as a virtual backbone (VB) for efficient routing and broadcasting in wireless sensor networks (WSNs). Currently, almost all existing works focus on constructing minimum‐sized CDS under the deterministic network model. However, because of the existence of many probabilistic lossy links in WSNs, it is more practical to obtain a VB under the realistic probabilistic network model (PNM). Moreover, load‐balance factor cannot be neglected when constructing a VB to prolong network lifetime. Hence, in this paper, we propose a multi‐objective genetic algorithm to construct a load‐balanced VB under PNM. Through simulations, we demonstrate that our proposed methods extend network lifetime by 69% on average compared with the existing state‐of‐the‐art approaches. Copyright © 2014 John Wiley & Sons, Ltd.