In this paper, the finite element analysis software ABAQUS is used to analyze the ultimate bearing capacity of three-dimensional rectangular footing of marine structures. The deformation law and the failure mode of homogeneous seabed soil beneath the rectangular footing are analyzed in detail. According to the equivalent plastic strain of soil under rectangular footing, an allowable velocity field of homogeneous seabed soil is reasonably constructed. Based on the plastic limit analysis theory of soil mass and by using the Mohr-Coulomb yield criterion, an upper bound solution of the ultimate bearing capacity of three- dimensional rectangular footing on general homogeneous seabed soil is derived, and a correction factor of ultimate bearing capacity of three-dimensional rectangular footing is given. To verify the rationality and applicability of this theoretical solution, some numerical solutions are achieved using the general-purpose FEM analysis package ABAQUS, and comparisons are made among the derived upper bound solution, the solution of Vesic, and the solution of Salgado et al. The results indicate that the upper bound solution of the three-dimensional shallowly embedded rectangular footing proposed in this paper is accurate in calculating the bearing capacity of homogeneous seabed soil. For undrained saturated clay foundation and sandy foundation with smaller internal friction angle, this upper bound solution can evaluate the ultimate bearing capacity of rectangular footing; with the gradual increase of the internal friction angle of the soil, the ultimate bearing capacity of the proposed upper bound solution is slightly higher than that of the rectangular footing.