Mănăstirea a fost inițial un schit, construit în 1828, de către familia Floroaia.
Purtând hramul Sfinților Împărați Constantin și Elena, biserica Mănăstirii Șoldana a fost ridicată în anul 1828 (după alte surse, 1850), pe temelia unei mai vechi bisericuțe ce slujea drept capelă la curtea boierească Floroaia, pe teritoriul căreia a fost construită, și a credincioșilor din satul Șoldana.
După al Doilea Război Mondial, sfântul lăcaș, care suferise mari stricăciuni, este reparat și din nou sfințit, la 26 octombrie 1948, de către vrednicul de pomenire Patriarh Teoctist, pe atunci exarh al mănăstirilor din Arhiepiscopia Iașilor.
În anul 1961, schitul este închis din ordinul regimului comunist, iar puținii viețuitori, alungați. Timp de peste 20 de ani, fostul egumen, protos. Ghenadie Aivănesi, rămâne singurul care se îngrijește, cu puținele posibilități pe care le avea, să întrețină sfântul lăcaș, până în anul 1987, când trece la Domnul, iar Sfânta Biserică este preluată de către Părintele Paroh Aurel Lunic al Parohiei Spineni, sat învecinat cu sfântul locaș, slujind aici o duminică pe lună și, uneori, la sărbătorile mari.
În anul 1992, la inițiativa Preafericitului Părinte Patriarh Daniel, pe atunci Mitropolit al Moldovei și Bucovinei, fostul Schit Șoldana se redeschide cu o mică obște de monahi trimiși de la Mănăstirea Cozancea, Județul Botoșani.
În anul 2001 este numit stareț al Mănăstirii Ieromonahul Nectarie Voroneanu.
Între anii 2005-2014 a fost renovată și consolidată Biserica Mănăstirii Șoldana. S-au făcut, de asemenea, veșmântar nou și pridvor, care s-a și pictat; a fost înlocuit acoperișul, iar lemnăria schimbată. S-a făcut o catapeteasmă nouă din lemn de stejar sculptat și icoane pictate. În curtea bisericii a fost construit un Agheazmatar și s-au refăcut aleile betonate. A fost construit gardul mănăstirii și s-a refăcut fântâna de la poartă.