In this paper, the rank-constrained matrix feasibility problem is considered, where an unknown positive semidefinite (PSD) matrix is to be found based on a set of linear specifications. First, we consider a scenario for which the number of given linear specifications is at least equal to the dimension of the corresponding space of rank-constrained matrices. Given a nominal symmetric and PSD matrix, we design a convex program with the property that every arbitrary matrix could be recovered by this convex program based on its specifications if: i) the unknown matrix has the same size and rank as the nominal matrix, and ii) the distance between the nominal and unknown matrices is less than a positive constant number. It is also shown that if the number of specifications is nearly doubled, then it is possible to recover all rank-constrained PSD matrices through a finite number of convex programs. The results of this paper are demonstrated on many randomly generated matrices.