The aim of this paper is to study the implementation of an efficient and reliable methodology for shape optimization problems where the objective function and constraints are not known explicitly and are dependent on the Finite Element Analysis (FEA). It is based on the Simultaneous Perturbation Stochastic Approximation (SPSA) method for solving unconstrained continuous optimization problems. We also propose Penalty SPSA (PSPSA) for solving constrained optimization problems, the constraints are handled using exterior point penalty functions within an algorithm that combines SPSA and exact penalty transformations. This paper presents a new structural optimization methodology that combines shape optimization, geometric modeling, FEA and PSPSA method to successfully optimize structural optimization problems. Several tests have been performed on some well known benchmark functions to demonstrate the robustness and high performance of the suggested methodology. In addition, an illustrative two-dimensional structural problem has been solved in a very efficient way. The numerical results demonstrate the robustness and high performance of the suggested methodology for structural optimization problems.