To address the poor resistance of recycled aggregate concrete (RAC) to chloride ion penetration and freeze–thaw deterioration in cold coastal regions, this study introduces basalt fibers (BFs) as a reinforcement to improve its durability and structural integrity. Rapid freeze–thaw and electric flux tests, combined with scanning electron microscopy (SEM), were employed to systematically evaluate the effects of fiber volume fraction and length configuration on the frost resistance and chloride impermeability of basalt fiber-reinforced RAC (BFRAC). The experimental results demonstrated that the incorporation of basalt fibers markedly enhanced the coupled durability of RAC, with the mixture containing 0.15% fiber volume and a balanced hybrid of short (12 mm) and long (18 mm) fibers achieving the most favorable performance. This mixture effectively reduced mass loss and strength degradation under repeated freeze–thaw cycles while substantially lowering chloride ion penetration compared with plain RAC. Microstructural observations revealed that the hybrid fiber system formed a multi-scale three-dimensional network, in which short fibers restrained microcrack initiation and long fibers bridged macrocracks, jointly refining the pore structure and improving the interfacial bonding between recycled aggregates and the cement matrix. This synergistic mechanism enhanced matrix compactness and obstructed chloride transport, leading to a more stable and durable composite. The findings not only establish an optimal basalt fiber design for improving RAC durability but also elucidate the fundamental mechanism underlying hybrid fiber synergy. These insights provide valuable theoretical guidance and practical strategies for developing sustainable, high-performance concrete suitable for long-term service in cold-region coastal infrastructures.