The application of animal-derived proteins as wine fining agents has been subject to increased regulation in recent years. As an alternative to protein-based fining agents, insoluble plant-derived fibers have the capacity to adsorb red wine tannins. Changes in red wine tannin were analyzed following application of fibers derived from apple and grape and protein-based fining agents. Other changes in wine composition, namely, color, monomeric phenolics, metals, and turbidity, were also determined. Wine tannin was maximally reduced by application of an apple pomace fiber and a grape pomace fiber (G4), removing 42 and 38%, respectively. Potassium caseinate maximally removed 19% of wine tannin, although applied at a lower dose. Fibers reduced anthocyanins, total phenolics, and wine color density, but changes in wine hue were minor. Proteins and apple fiber selectively removed high molecular mass phenolics, whereas grape fibers removed those of both high and low molecular mass. The results show that insoluble fibers may be considered as alternative fining agents for red wines.