In this work we report results of continuous wave (CW) electron paramagnetic resonance (EPR) spectroscopy of vanadium oxide nanotubes. The observed EPR spectra are composed of a weak well-resolved spectrum of isolated V(4+) ions on top of an intense and broad structure-less line shape, attributed to spin-spin exchanged V(4+) clusters. With the purpose to deconvolute the structured weak spectrum from the composed broad line, a new approach based on the Krylov basis diagonalization method (KBDM) is introduced. It is based on the discrimination between broad and sharp components with respect to a selectable threshold and can be executed with few adjustable parameters, without the need of a priori information on the shape and structure of the lines. This makes the method advantageous with respect to other procedures and suitable for fast and routine spectral analysis, which, in conjunction with simulation techniques based on the spin Hamiltonian parameters, can provide a full characterization of the EPR spectrum. Results demonstrate and characterize the coexistence of two V(4+) species in the nanotubes and show good progress toward the goal of obtaining high fidelity deconvoluted spectra from complex signals with overlapping broader line shapes.