The paper deals with the multi-objective optimization problems of laminated composite beam structures. The objective function is to minimize the weight of the whole laminated composite beam and maximize the natural frequency. In particular, the simultaneous use of all the design variables such as fiber volume fractions, thickness and fiber orientation angles of layers is conducted, in which the fiber volume fractions are taken as continuous design variables with the constraint on manufacturing process while the thickness and fiber orientation angles are considered as discrete variables. The beam structure is subjected to the constraint in the natural frequency which must be greater than or equal to a predetermined frequency. For free vibration analysis of the structure, the finite element method is used with the two-node Bernoulli-Euler beam element. For solving the multi-objective optimization problem, the nondominated sorting genetic algorithm II (NSGA-II) is employed. The reliability and effectiveness of the proposed approach are demonstrated through three numerical examples by comparing the current results with those of previous studies in the literature.