In fluorescence molecular tomography, the accurate and stable reconstruction of fluorescence-labeled targets remains a challenge for wide application of this imaging modality. Here we propose a two-step three-dimensional shape-based reconstruction method using graphics processing unit (GPU) acceleration. In this method, the fluorophore distribution is assumed as the sum of ellipsoids with piecewise-constant fluorescence intensities. The inverse problem is formulated as a constrained nonlinear least-squares problem with respect to shape parameters, leading to much less ill-posedness as the number of unknowns is greatly reduced. Considering that various shape parameters contribute differently to the boundary measurements, we use a two-step optimization algorithm to handle them in a distinctive way and also stabilize the reconstruction. Additionally, the GPU acceleration is employed for finite-element-method-based calculation of the objective function value and the Jacobian matrix, which reduces the total optimization time from around 10 min to less than 1 min. The numerical simulations show that our method can accurately reconstruct multiple targets of various shapes while the conventional voxel-based reconstruction cannot separate the nearby targets. Moreover, the two-step optimization can tolerate different initial values in the existence of noises, even when the number of targets is not known a priori. A physical phantom experiment further demonstrates the method’s potential in practical applications.