This study investigated the origin of the enhanced pseudo-elasticity of additively manufactured vanadium carbide-containing Fe-based shape memory alloys. The aged samples with two different starting microstructures, as-built and solution-treated, showed completely different final microstructures following identical aging treatments. The sample aged directly from the as-built microstructure exhibited typical solidification structures, molten pools, and cellular structures with fine grain sizes inherited from the laser powder bed fusion process with a high cooling rate. In contrast, the sample aged following solution treatment revealed fully recrystallized grain structures with relatively larger grain sizes than the former. Despite having the same type of carbides, the directly aged sample had finer and denser precipitates than the sample aged following solution treatment. Additionally, compared to the sample aged following solution treatment, the directly aged sample exhibited a larger pseudoelastic recovery strain. The precipitation behavior may have had a negligible impact on the pseudo-elastic behavior because the increase in the pseudo-elastic recovery strain following aging treatment was not significant for either sample. Besides, thermodynamic calculations predicted that the stability of the face-centered cubic (fcc)-gamma phase would be increased by local elemental segregation at cell boundaries. Cell boundaries with high fcc-gamma phase stability can act as sites that can apply back stress on the deformation-induced hcp-epsilon phase, thus promoting reverse motion of the Shockley partial dislocations or deformation-induced hcp-epsilon phase. Furthermore, the smaller grain size enhanced the stability of the fcc-gamma phase.