A new algorithm for the least squares (LS) solutions within the Vector Fitting (VF) method is proposed in the paper. The algorithm is based on QR-factorization, which exploits the specific structure of the VF matrix. Numerical experiments confirmed an essential reduction of the computational efforts. Besides, the new algorithm ensures a better accuracy and requires considerably less memory than the standard Matlab sparse solver. The special form of LS matrix (left part of the matrix is block-diagonal with identical blocks) in VF problem allowed us to propose a more effective linear solver, than the standard one. The efficiency of the new algorithm is achieved due to replacement of the full matrix QR factorization by the following sequence of operations: QR factorization of the block; orthogonalization of the right part of the matrix with respect to the obtained block of Q matrix; QR factorization of the orthogonalized right part of the matrix. It was experimentally demonstrated that in order to ensure sufficient accuracy of the solver it was necessary to perform reorthogonalization of Q matrix of the right part of LS matrix and to perform QR factorizations with column permutation. Testing of the developed solver and its comparison with the standard solver was done for two data sets. The testing results showed that the new solver allowed us to reduce CPU time by the factor up to 50 for sufficiently large sizes of LS system. In most cases the new solver ensures less value of the residual norm than the standard solver and a better accuracy. The advantages of the new solver become even more impressive with an increase of the size of the system.