Fire protection has been a major challenge in wood construction for many years, mainly due to the high flame spread risk associated with wood flooring. Wood fire-retardancy is framed by two main axes: coating and bulk impregnation. There is a growing need for economically and environmentally friendly alternatives. The study of polyelectrolyte complexes (PECs) for wood substrates is in its infancy, but PECs’ versatility and eco-friendly character are already recognized for fabric fire-retardancy fabrics. In this study, a new approach to PEC characterization is proposed. First, PECs, which consist of polyethyleneimine and sodium phytate, were chemically and thermally characterized to select the most promising systems. Then, yellow birch (Betula alleghaniensis Britt.) was surface-impregnated under reduced pressure with the two PECs identified as the best options. Overall, wood fire-retardancy was improved with a low weight gain of 2 wt.% without increasing water uptake.