The increasing use of complex designs in structural and infrastructural systems necessitates the development of accurate and efficient approaches to address the many uncertainties that arise in the design process. The uncertainties (e.g. in the environmental loads, structural parameters, boundary conditions etc.) can severely affect the performance and integrity of the expected design, causing structural failures and subsequent economic and societal distress. Reliability-based optimization (RBO) offers a rational framework for safe design under uncertainties by including the structural reliability measure as constraint into the design optimization problem. In this study, we present a stochastic search algorithm for the RBO problem based on the cross entropy method (CE). The CE method is an importance sampling technique originally developed for rare event estimation. Based on the idea that locating the optimal solution in the feasible design space can be viewed as a rare event, we aim to adapt the CE-based importance sampling method to tackle the RBO problem. Constraint handling is a crucial step in design optimization. To this end, we explore novel strategies to efficiently incorporate the structural reliability constraints in the generation of samples during simulation. The aim is to deliver a black-box algorithm that intelligently prioritizes the feasible solutions and, simultaneously, optimizes the objective function in a natural way.